I mained paladin up to 3.5 and it's probably the easiest to play effectively. I only played warrior enough to get foresight and bloodbath. DRK is kinda above my skill level tbh, but it's super fun to play as OT eventhough it's not really built for it.

As I decided to level my warrior. I kinda fell in love with it. You get to see big numbers(11k crit fell cleave anyone). Aggro is very easy to maintain and the skill floor is between pld and drk.

I would recommend leveling pld first to get provoke, but that will all change with 4.0. Aggro is kinda bad until 40 on pld, but war/drk gets tank stance at 30.