Well, I'll go through the list, I have 7 80s so I know what im doing.
Hunters - Yes, Good solo, quick damage. The pet tank makes for no down time, since you get aspect of the viper at low levels now ( gives lots of mana), good damage in pvp. Dominates pvp up to lvl 60ish.
Warlocks - Same boat as hunters, Voidwalker can keep aggro enough to kill a mob if you give it half a second. Can spec for lots of dots ( damage over times), or burst damage.
Priests - Up too 40 they are SLOW. Once you grab shadowform, they are fast ( increases dmg by alot, increases your shadowhealing, ect). With the buff to VE, you can keep yourself healed with damage ( vampiric embrace). Disc is great in pvp, hard as hell to kill at low lvls.
Shamans - Enhance is very fast, once you hit 75, spec ele for lava burst, and you will 2 shot things. Some down time before shamanistic rage in enh.
Druids - Feral/boomkin are both very fun and good leveling, Resto is slow as hell. Boomkin is pretty much a mage, feral being a mix between warrior and rogue. All 3 specs are great in pvp.
Warrior - Hard class to play, has good damage, but also takes alot of damage if not speced prot. Tricky class, wouldnt recommend for newby.
Rogue - Fun class. Good in pvp, with alot of cds. However can be slow in pve due to the amount of damage they take, and it is hard to kill higher level mobs with them.
Pallys/Dks - Dks are amazing, Cant die in pve, tank, great damage, ect - Hard to learn pvp. Pallys can spec for anythign, holy is hella slow, but good in pvp. Prot/ret are both very fast lvling specs, and both roll on pvp.
Mages - VERY fun. I levelled mine to 80, and had a blast doing it. All 3 specs are fun, Frost being the pvp spec. Arcane is great past 60ish, fire being a raid spec. I would level frost. Lots of kiting/dmg. However you do have down time.