Mine was the warlock class, after finally giving up on my druid (the first time). The druid class seemed to promise some very interesting class quest, which never really materialized. The warlock class had me keeping an infernal running after me for the length of Felwood while I slowly whittled it down to size. I'll never forget banishing farmer's (and regular folk) demons that they were trying to kill. It is a shame (or sham, take your pick) that Curse of Doom can't be cast on players (Blizzard could even change it such that anything that can remove a curse would have a 100% success rate at removing it and I'd be happy). Perhaps the warlock class has lost most of the flavor it had awhile ago, I haven't tried leveling one up recently.

I think second would be the priest class. The first one I leveled (ages ago) I was on a server with a very small portion of healer classes. Groups followed me, if someone was a prick and not playing well, I could be an even bigger one by threatening to leave if we didn't put in a replacement I had on hold and waiting at the instance portal.