Hunter is a good class to start out with. They were rather powerful recently, but have been hit with the nerf bat a few times. Still a solid class, though. They are very capable for handling PvE enemies and such thanks to having pets to manage aggro, strong ranged attacks, good survivability with mail armor at later levels, and more. And, they are very capable in PvP thanks to a pretty deep bag of tricks. They do very well in Battlegrounds (a form of PvP), but are the least successful class in Arena according to some recent statistics...I suspect that it's largely because the arena is too confined for them to be effective. Hunters, Warlocks, and Paladins are probably the most capable solo classes.
Rogue is another good class to start out with. Stealth abilities provide alternatives to many situations that might otherwise be difficult or time consuming. They make things die quickly, have good escapability, create advantageous situations in PvP and avoid disadvantageous ones....pretty fun all around. If you want to be a griefer on a PvP server, this is THE class.....
I would rank Mage a notch up in complexity...they are playable with a beginner but will probably get killed a number of times learning their limitations and how to utilize their capabilities. There can be a lot of advanced play in using them.
As complex as Paladins can be and have a tricky time filling roles in 5-man groups and raids, they can be extremely fault tolerant for a beginner. Being a melee class in mail and later plate armor, capable of healing themselves AND throw up invulnerability bubbles...a person can do a LOT wrong and still survive and win. They are extremely powerful in PvP and are all the most successful and utilized class in Arena.
The basics of Warriors are very simple and easy, but they are also very nuanced for advanced play. Lots of limitations place a heavy emphasis on efficient, flawless play and their roles in 5-man groups and raids as main tank is normally the most difficult and high pressure job in the group. Generally...they start out being fairly good for beginners but can quickly get very frustrating at middle levels and beyond.
Warlock isn't bad to start, but won't shine until learning the game pretty well.
Stay away from Shamans and Druids until later...I started my first character as a Druid and ended up shelving it...as a more advanced player I love the class again and go back to working on the player off and on. Shamans are even trickier.
Priest is pretty easy to start out with IF you have someone to play with all the time that can manage aggro and do the bulk of the killing. Playing a priest by yourself becomes rather challenging in a hurry much past level 20. Put a Priest and a Warrior together and they look at each other with big doe eyes and say, "Where have you been my whole life?"