I have a 80 paladin and it's pretty nice to play, I am a tank and overall it's fun and paladin can for sure be main tank without problem (they are considered the best class at it right now actually).

My main is a lock and I do agree with Jas2davir that they are somehow becoming rare, I very often end up being the only one in the raid even when pugging VoA or something.

In general there is a lack of some clothie dps and wayyyyy too many plate dps (loldks), so you need to decide what you wanna do, if you are you sure you want to dps only, mage can be nice (lock as well but thats not in your list ^^).

If you are not sure yet and would like the flexibility at 80 to do other thing than dps, I would say go paladin, you won't really regret it. But if you want to be a ret paladin only, you are going to be a drop in the middle of the sea....