You can level in BfA without doing the war campaign at all now so personally I recommend that one because it’s the best part of the entire expansion and the meta-achieve for Pride of Kul Tiras and Zandaladar Forever is a great journey.
WoD has a bad rep but the levelling story was actually pretty fun and it’s very quick XP, you get some weaker points in Talador and Gorgrond but overall it’s enjoyable and is very, very quick for levelling.
Cata is so vast in terms of the zones that you can’t really compare it to the others, you’ll be going zone by zone as opposed to completing every one. I would recommend Vash’jir, Cape of Stranglethorn, Duskwood (for Alliance), Silverpine (for Horde), Southern Barrens, Stonetalon, and Blasted Lands.
MoP is just flat out the same degree of quality throughout, you can’t really go wrong there. It lacks all the same bells and whistles that WoD onward had but it’s quite well done with many memorable characters.
Legion is alright but the strongest parts of it weren’t the levelling zones but rather the Suramar arc, so you’d level out before you got to that I figure.
Wrath is the pinnacle of the old, pre-Cata style of writing that in my opinion was largely superior, at least for worldbuilding and coherence. Consistent quality throughout, much like MoP, and a nice grounded xpac with a gothic middle fantasy vibe.
Aaand TBC, again using the old style of writing. Honestly for story it’s again kind of a mix, with some cool aspects to it, and overall the quality is consistent, but it doesn’t have as much coherence as Wrath. Hellfire, Nagrand, and Blade’s Edge Mountains all have some excellent quests, and Zangarmarsh is very atmospheric and alien. Netherstorm and Terrokar I’m not quite as fond of, but they also have some interesting stories to explore.
Really, there are things to enjoy in every expansion, story wise it’s honestly a rare thing to have the levelling content not have decent stories, so it comes down to your preference.