I would prolly go with the mage if I had to pick from that set of options. Free food/water to save coin. Ports to speed things up, you can set your hearth to one place and port to Dalaran. Any class is capable of doing 90% of the content out there and even some of the group content as well. Northrend is pretty good for leveling with the daily quests. You can pretty much start with the 3 daily quests from the walrus guys. The quest to spear the drake by the Nexus is fast and easy. The other two in Howling Fjord are quick and easy. As you get a few levels there are tons in Grizzly hills you can add. Some are not exactly MB friendly but as solo you should be fine.

http://www.wowwiki.com/Daily_quest

I would hammer out the Grizzly Hills and lower dailies till you get sick or level to 80 off of them. Run a few pugs and explore around. When you get to level 78ish, I would hit up Icecrown. There are a ton of dailies and you will prolly be level 80 by the time your are done unlocking them. There is also the Argent Tournament as well.