How big is WoW? Kalimdor is about the size of Manhattan. But I don't mean 'physical' size. I mean your perception of it. This is important for creating the perception of being in a world.
We can measure size by time. How long does it take to get from here to there? When you can only run, the Barrens are huge. When you have regular riding, it's still pretty big. With epic riding it's still big. Maybe picking the biggest vanilla zone was a bad example. Let's run from Crossroads to Camp Taurajo instead. On foot it's a decently long run. Riding, not so bad. Flying they're right next to each other, no distance at all.
Speed makes the world smaller. When you bring places closer together (at least in our minds) and you lose more and more of the space between you also lose some of the world.
If it's hard to move between places, they seem further apart. Think of running through STV. Look at the area next to Lake Nazferiti. Here's a map. You could take the path curving around or you could take the straight path from one bridge to the next; we're going from the bottom of the lake to Nesingwary's camp. The path is longer, right? By perception, maybe not. Cutting across in your 30s or 40s will lead to a lot of mobs attacking you. Even if they don't daze you, you might find it taking longer as you try to dodge around them. If you are dazed, then you have to fight them.
While it's true that effort is indirectly increasing time, I feel it's worth dividing between your possible movement speed (running vs. mount) and your average speed (mounted vs. fighting). At an extreme example imagine a pack that you could not simply run through, it would automatically dismount you. Or even an area that needed a group to fight through it. Think of an instance; they're actually quite short, even the ones we consider long, it's the fighting which makes them seem long.
There is some mix of blocked and free sight which gives the greatest perception of distance. Too much blocked sight and you have zero context. Too much free sight and then "oh that's not so far away, it's right there." A mix would give an idea that things are some distance away, but nothing is right here within sight.
The terrain there is excellent. The hills and trees and all that break your line of sight, reducing the problem in so many other zones of complete enemies right next to each other(see SMV for some of the worst examples). Sure, the zone could just be bigger, but that means more space to fill in (unless you're a fan of flat, featureless terrain) and more time spent riding around.
The hills and the wolves in them encourage the player to stick to the paths if they want to be safe, but if you're willing to dodge trees and wolves and who knows what else lurking, you can cut across and maybe save some time. Finding a path without a marked path can be tricky sometimes, but you won't find yourself stuck like in Ashenvale where attempting a short cut means a ten minute mob-filled run parallel to the road, trying to find where the random ridges end.
Flying kills size and terrain. You can see everywhere and nothing is far away. Mobs don't phase you. Hills are nothing but sights, not something which actually affects how you move. You pick and choose where to go with nothing in between. Flying effectively removes you from the world, it makes you a disconnected observer rather than someone interacting with the world.