Frost: Very safe way of leveling. Higher survivability, though lower burst damage. One very big advantage to leveling Frost is in Outlands, you can frostbolt kite shit by yourself on quests that usually recommend 3 people to do. Makes it very easy to get your mobs under control with Cone of Cold, Frost Nova, and Arcane Explosioning shit just out of melee range while they're snared.
PvE ezmode.
Fire: High burst damage. Great for burning shit down quickly, especially against members of the opposite faction. Though PvP Frost builds may be all the rave at 70, deep Fire can make you put out a lot of DPS. Not very mana efficient.
I actually leveled Cort up as 21 points Arcane, the rest Fire when I first started playing a Mage. I just wanted to burn shit down, and still be a viable adversary if Alliance tried to gank me. While you can probably take on more mobs at a time as Frost, leveling as PvP Fire really helped me get a good understanding of just how frail a Mage is. If you happen to have a healbot with you, you won't believe how quickly you can AoE shit down as Fire, however.
Arcane: Played around with it for a day or so, wasn't my playstyle, so can't offer you an unbiased opinion. If you want my biased opinion from that day of play, it makes you somewhat of a utility Mage, but for leveling up, you're just not going to have the gear and enough Intel to justify primarily spec'ing into Arcane. Maybe up to Presence of Mind if you want to be able to nuke Horde/Alliance trying to gank you mid-pull. Other than that, I'd wait till you're 70 to play around with these specs.