In Pursuit of Something Fresh!

So it seems I'm back on the WoW ride and I'm feeling like trying some new things this time around. My main was a rogue in Cata before the Moltdown and my WoW knowledge is fragmented and scattered somewhat evenly among all expansions.

Having said that, what class + spec would you guys recommend for someone seeking to play something more elaborate, refreshing and rewarding? Something that makes you go "Damn, I wish people gave X a chance because it's actually very, very interesting and satisfying to play!". I truly don't care about its reputation or it's restrictions in terms of comps: just be brutally honest!

It can be in any of the expansions available, and I'll admit I mostly PvP but interesting PvE rotation and such might lure me in as well!

Warlock: Affliction / Demonology - WotLK (PvP) / Cata (PvP)

Warlock, for me, was the hardest class to level and learn. I created and deleted so many of those damn things over the years until finally it just kind of clicked; only 1/3 of your spells are active depending on which spec you use and demons need to be thought of as walking spell books. Once I realized those 2 things I finally reached 80 and played it through WotLK and in to Cata, 4.2 patch.

It's very rewarding to play a warlock in endgame content because it's a class that everyone tries but few stick with.
You need to manage DoTs, demons, drains, soulstone, health/mana, and fear; all while having almost no mobility and very few instant cast direct damage spells. Often times your health bar is your only defense.

Affliction: You have to learn patience and discipline to play this well; patience that you'll have to DoT everything that moves and discipline that you have to keep those DoT up at almost all times. Once you realize that time is on your side affliction can be very fun to play.

Demonology: A lot of utility here. Most players just stick with one demon but in my experiences juggling demons can be very potent. When a melee gets in your face use metamorphosis and they'll back away quickly. Power through dominance is how I'd best describe playing a demo warlock.

I would say protection paladin for PvP. Main reason I like this combo is cause 1 skill can interrupt, daze, and silence! So damn sexy :D

Thanks for the suggestions, I'll keep looking.