I started leveling as Arms, then got Whirlwind Axe and continued leveling as Arms.
With lvl42 it was a lil bit boring and I got that polearm from Uldaman (lvl42), because of its speed (2,7) I leveld 2h Fury then.
Wasn't too bad (but not as good as Arms with WW-Axe) and I thougth NVM til lvl51 I will play with it because of the weapon skill for Ice Barbed Spear.
lvl 51 --> No Spear for me because of the "highlevel" Players always talking shi.t to the "Korrak-Hopers".
I bought a Flurry Axe and played DW then with Thrash Blade in my MH.
Was the most single target damage I had til then, with +1% Hit (Hinterlands Trinket).
Because it was so good I even decided to buy Axe of the deep woods, which was a really strong combo for me even for lvl60 PVE in the future (orc, pre60 not worth the +5 Skill, but at 60 still very viable weapons pre Raid).
The thing about DW was for me, that World-PvP became a pain. No MS, No fat burst with Crits on cloth-wearer and so on.
I leveled til lvl55 with that combo. Killing mobs was really smooth, pvp was a pain.
I went another time into AV and got the Spear --> Specced Arms again and now I am happy.
Killing mobs is not as fast as with the two 1h Axes BUT I got more burst (some mobs die really really fast) and MS for PvP and Sweeping Strikes for leveling.
Cleaving mobs with Fury was not so cool as it is with SweepingStrikes. For leveling it is really cool and nice. Even for dungeons as DPS its brutal to cleave the thrash mobs with it ^^
I would recommend Arms for leveling. Fury on a Pve-Server I think. But here you will be ganked (Nost-PVP) and IMO as Fury you dont have a chance then