Horde will have the easier leveling experience. Everything’s right there in The Barrens and surrounding areas especially up to 30 or so while Alliance will have to hop from Westfall, Loch Modan, Wetlands, Darkshore, Ashenvale just to find quests. Many of their questing areas have flight points in very convenient places (looking at you, Grom’Gol).
Even the instance grind is easier. Horde have a dungeon in Org (that drops loot), Wailing Caverns, Shadowfang Keep, Razorfen Kraul, Razorfen downs, and the entirety of Scarlet Monastery on a main city’s doorstep. They get easy teleporter access to Gnomeregan and a flight point basically right outside Blackfathom Depths. Their FP in Desolace IIRC is also fairly close to Mara.
Alliance have deadmines and Stockade (drops no loot), then usually don’t bother much with dungeons until SM because BFD and RFK and SFK are so out of the way. SM is also very out of the way but it’s so good for drops and EXP that they suffer the ~15 minute run anyway.
I’ve had friends that have gone from 1-60 on both sides who have said horde is definitely smoother. Less foot travel time, less time running to important places from FPs, more time questing and dungeoning, more time actively killing = smoother experience.
Not really going to go over racials, just alliance tend to have far more situational racials with more of a PvE skew. One point here is if you are human (or orc) and you are a warrior (or shaman I guess), you won’t have to buy edgemaster’s handguards, which are a couple thousand gold at max level if you plan to raid DPS (or warrior tank). The +5 weapon racial is probably the strongest PvE racial, or close to it.
PvP-wise horde tend to have higher wait time due to being the more populated faction in most cases. If you want something like the ice barbed spear, it’s very easy to get an AV win on horde where on my BG Alliance have gone from zero to exalted without a single AV win. The rep is faster for Alliance, however.