Your mass plus the acceleration of gravity gives a Force vector (F_{you})that, when you stand straight up and down, is directly opposite the normal force, correct? But, when your legs spread wider than your shoulders (when you get an angle in there), you can decompose F_{you} into a vertical and a horizontal force. Normally, when you do the splits, the horizontal component of that vector is opposed by your own leg muscles (your abductors) and by the friction of the surface. When you're on a low-friction surface (or a no-friction surface), the horizontal component of F_{you} is opposed only by your own muscles, which makes walking much more fatiguing.
Now for a less physicsy explanation. ;)
True, your normal force is always your weight. But what is walking, really? Typically, it's falling (with style) -- a controlled fall. You shift your weight forward and as you fall, you bring a leg out and you land on that leg. You then shift your weight forward and as you fall you bring your other leg out and you land on that leg.
When you really don't want to fall, you can put your leg out in front of you then slowly shift your weight from leg to leg, but this is slower, it's not how we normally walk. But when you're on a low friction surface, it's easy to see that it's difficult to shift your weight from leg to leg if you're almost doing the splits, if your legs are far apart.
If you're walking like normal, it's also easier to "catch" yourself if you're only falling for a short distance, if you take smaller steps.
Also, when you take smaller steps, you don't have to use your leg muscles as much to prevent yourself from doing the splits as you're walking. Normally, surface friction helps to stop your legs from skating out from under you.
