Wall of text incoming! This was my first character, just like back in TBC when I started. Druid was my “first love”, so to speak, and back then I leveled on RPPvP. Went RPPvE this time around - and did not just focus on my druid. Unfortunately I have little time to play, which is why I have only 1 lvl 60 (and a crappy geared one at that).
Leveling on druid was pretty much as I remember from back then, slow until bear form. Then it picks up. This time around I alternated between caster and bear form (go bear until I need to heal, then stay in caster until mana is lowish, then bear again etc) until lvl 20 and cat form. Druid picks up a lot then, especially with the speed boost talent. It got a bit slower in the last 15 or so levels. The lack of Mangle at lvl 50 is very noticable compared to TBC, as is the lack of a reliable interrupt for casting mobs (bear form>bash takes up mana).
I have a Warlock close to 40, leveling is quick and easy so far, lots of damage and quality of life. Especially once you get Voidwalker, it picks up a lot and remains pretty good up to now.
I also have a Warrior near 40. I’ve kind of given up on him, but I am actually leveling a new one, Undead this time around because I felt like it
It feels quite strong early on and 1H/shield felt good until 20-something in terms of speed, as it allows for survivability… However it starts to become very slow. Dual wielding is a nice change of pace. It’s not too hard, as long as you kind of think like a rogue - picking your fights, minding the terrain, isolating your target etc.
My rogue is 51, and it’s a blast! I didn’t expect to enjoy it as much as I am. It has a good pace, especially if you can keep your weapons updated, as well as reliable interrupts, fun abilities and a ton of escape options. Funnily enough, my favorite aspect are the non-combat rogue professions, lockpicking and pickpocketing. They are good gold makers and have a wonderful RP factor as well.
I have a Shaman at 34. It’s a strange one. Sometimes I feel super motivated to play it, sometimes I just go “eugh”. I think the best way I can describe it is that I don’t feel as much powerful as I do capable on him. Shaman has a ton of tools but a limited mana pool, which makes it imperative to plan which abilities you’ll use for each fight. This gives it a more pro-active feel, which is pretty interesting.
My Troll Shadowpriest is 44, and I think it may become somewhat of a main. I really am in love with it. Once you get a wand and manage to keep it kind of up to date, priest leveling is steady, predictable and kind of easy. It really takes off when you get shadowform, you suddenly go from a steady but kind of dull leveler to quite the beast, especially if you pick up stuff like the Dreamweave armor. What I find especially enjoyable though is mind control. It’s a blast to use, and mind soothe makes up for its shortish range.
I can’t seem to get into Hunter, even though it’s a super flavorful class. Same goes for Mage. Shame really 
As for paladin, I don’t play Alliance so I haven’t gotten one over 28. I did like it, strangely enough, which is why I’m waiting for TBC.