I’m actually not so sure about that. Cataclysm was the end of an era of WoW design in many respects, and the design principles became closer to what they are in retail now. So they might as well leave it at Wrath, and look for some ways to stretch out that experience further.
More or less. The Alliance had more areas than the Horde before Cata, and Blizz decided to cut them out of zones like Hillsbrad rather than add Horde content to former Alliance zones. Then there was the fact that the story in these zones often ended in clear Horde victories, with quite a few Alliance hubs or keeps razed in the process, while persistence against the Horde was pretty much as good as it got for the Alliance, and small victories like Camp Taurajo were regrettable accidents that were viciously avenged by the Horde.
And most importantly… the Alliance only content in the leveling zones was partially ridiculous parody, with references to things like CSI or Rambo taking up a lot of the new quest content, while Horde content didn’t have the same problem. Even worse, some zones were just obviously unfinished, like Arathi, which was left with a smattering of its old quests and not much else.
The endgame zones were less uneven, though not necessarily better. Well… to a point at least. Thrall was very much the focus character of most of the patch story, so even though vicious war was raging, Alliance players had the pleasure of helping Thrall save the world.
I guess the Firelands patch was more druid and night elf focused, though… Which is why we got to raid a Night Elf racial leader. But that was facilitated through the Cenarion Circle, so the Tauren druids had their role in the story as well, so I don’t think it was particularly bad for them. (Oh, and on the topic of raiding racial leaders, we also got to kill Stormwind’s Archbishop in some dungeon, while the plot behind his fall was largely cut. Not exactly uplifting, either.)
All in all… I would indeed assume that the Horde had the better experience there. By some margin. Now, I guess as someone who mostly played Alliance back then I might have some biases, but there really was a lot of imbalance in moments you were made to feel proud of on either side.