Which classes have fun play styles?

Okay, im going to start this of with stating that I'm not sure if this is the proper forum to place this question in, but its a general question. I'm currently playing tbc, and my playstyle usually revolves around me just trying to have fun playing every class, and slowly making my way to end game. From my previous playthroughs of wow, i tend to lose interest once i hit max level, and while i do do some end game content, its not really my focus. I currently just plan to go through every expansion and enjoy the story while i play through it multiple times with various classes.

Now to the specifics of my question, which classes are considered fun to play, and specifically which class specification is considered fun to play? For instance, I have 3 characters, as of right now. A BM hunter, Holy Paladin, and a frost mage. I chose these classes as i feel that they would be the most fun from what i could tell, but all of my sources of information only care about late-game content and which classes are better than the other in specific situations and what not.

As of right now, I plan to have a single class for my entire run of tbc, and then do the same thing in the later expansions that i play.

The main reason why I'm asking is because I'm currently having a boring time with my paladin, while I'm having an amazing time wtih my hunter. Is it just a difference of class, or did my choice of holy-paladin make that happen? Oh, and lastly, if there are any class specs that are amazing at soloing, I would definitely be interested in that. And i dont mean just late game, but possibly early-mid game as well. The main rason why i love my hunter is because of how much i can solo and do by myself, as long as i properly manage my pet

I was going to suggest Frost and Hunter but... yeah.
Warlock I would suggest, It has some nice life drain, also have a tanky pet "voidwalker", you get warlocks pets from quest chains with a little cool story to it as well.
Druids are a very versatile class as well, I leveled as feral and it was fun, Apart from other classes where leveling feels more like a chore.

We all have different playstyles and classes we like, Some like melee dps some love range dps, some love healing and supporting while some wanna tank, I think you like Range dps from what you choose so far.

If you want to try a melee class for once Warriors are very powerful but slow levelers due to the time they have to spend eating every pull.
Rogues are about the same but with a little bigger aresenal of abilities to save you, lower armor so you take more damage but stealth and stuns to compensate, I thought Rogue was fun to level, (as sub with 50% ambush critical chans).
Enhancement shaman is what you wanna level as if you solo quest as shaman, its a fairly easy melee class to level due to the healing spells you have.
Feral druid also as I posted very different with the shapes you can swap back and forth in combat to give you the upper hand of the situation, a skilled druid is very powerfull.

PvE I've always had an engaging experience as a rogue, PvP I'm finding I have a lot more fun on my mage than anything else. I had zero issues leveling a rogue, sure, you can't really heal besides the usual potion, first aid, food, but you won't need to nearly as much as similar classes because of your cc and infiltration abilities. Pack of mobs guarding the cave? You don't need to brute force in like a warrior... slip in, kill the quest objective and sneak out. There are even elite mob quests you can solo by evasion tanking and stun/disarm ability.

I wouldn't exactly say that my preference is range dps. I'm a tad bit annoyed with my frost mage, right now, as hes about like 25 and hes taking forever to level up. I've already spent 4 times longer on him then i have on my hunter, yet my hunter is higher leveled and could casually solo elite mobs. Granted, i understand that he'll be more fun to play later on, hence me taking the time to grind him up :/

In regards to rogues, I just made one, and im a bit uncertain about what to spec him in. Nothing i research about tbc rogues is giving me a concrete idea, so any help would be useful ^_^. Learning the rogue mechanics is a bit fun, but also confusing, but that may be because i just started the class. In all honesty, stealth solo games are some of my favorites, and that bleeds into me going about a mission as stealthily as possible, even as a non-rogue. I like to solo missions, picking enemies off 1 by one if possible, and being able to comfortably defeat 1-2 mobs if i get ambushed, or have an escape route ready. Thats actually why I'm irritated at my pally.

Hes tanky enough to last awhile, but he bleeds through mana, and if i hit oom, I may as well be dead, even to some normal mobs. Granted, im constantly trying to fight mobs that are either my level, or 1-2 above, but i should still be having a smoother experience, IMO. He just doesn't do enough damage, in the amount of time that I'm tanking, but hopefully that'll change once i get a higher level. I don't need record breaking dps, but if i can either get something to improve my mana situation, or to give me a bit more passive dps, that'd be godsend.

Its just my opinion, but for me the truth is that Hunter is just the best lvling class no doubt. He is a bit ahead of some classes and far away from the rest, so compared to Hunter you'll feel every race to have hard and ****ty lvling. I had fun with mage, rogues, shammy, even warriors

if you never tried warlock i suggest too...

we are very strong in this expansion pve wise and pvp wise...

all 3 specs can be viable (depending on the situation), and WOTLK warlock may be the strongest warlocks have ever been.

again if you never tried it, its worth it.

Feral druid and enhancement shaman are the best leveling classes by far. You can take on multiple mobs as well as elites and use most of your mana for healing only. Overall you spend the least amount of time eating and drinking. Mage is a close second but very dull, you just spam blizzard and keep kiting with blizzard until every mob is dead.