For what its worth I am talking like the first 2 weeks to a month or so after it went live. I have no idea what went on after that. I would believe as time went on grouping / questing got better.
Don't forget that a lot of the quests at higher levels were quite damn grind intensive. Remember Tirion Fordrings questline? First 3 quests:
Kill 30 Bats
Collect 15 worm asses
Kill 20-30 dogs
and then it just progressed in the same sense. I'm fairly sure that no one strictly grinded, there were a lot of quests that were worth doing, but overall you didn't quest ONLY. I know for a fact that the best way to level 35-43 or so was by grinding rock elementals in badlands (especially for shadow priests) - unless you take into accord that doing it as alliance on a pvp server sucked ass (didn't stop me from doing it, though)
Other good grind spots were the shimmering flats from maybe 28-33 or so, especially for horde. Tons of shit to just continously kill and quests that worked well in concjunction.
To those of you who say that dungeons were great, I don't think you remember how all those dungeon quests had you moving all over the world to get them. For example:
Wailing caverns - quests from ratchet, a pre-quest that took you to thunder bluff
Scarlet Monastery - why not go to desolace first? Horde had it better, just holla at varimathras
Razorfen kraul - main quest from thunder bluff
Zul'Farrak - The mallet to summon Gahz'rilla required a lot of traveltime in Hinterlands
Sunken temple - hakkar quest had you first go to feralas, then zul'farrak, then hinterlands to finally be able to do this boss. All quests for this place sucked
Uldaman - why not go in and out and in and out 3 times to do the main quest? Or for horde, take a trip to say hi to Thrall
Blackrock depths - Main quest gad you going in and out a lot. Still tons of quests, by far my favorite dungeon to date as well
Good dungeons:
Shadowfang keep - quick, 3 quests. One had to be delivered in UC, though.
Blackrock Depths - even though most quests sucked (I like the one that made you die, though), it was still fairly effective
Stratholme - tons of quests, fairly hard though. Nothing you did while leveling, except maybe 59 if you had a good group