Make a warrior for each race and play them a bit for a few lvls. See how they move, attack, laugh, run etc.
Know that you will be staring at their backs for a long time. Pick one you like most.
Go prot for early lvling - fast dungeons, good at pvp ( as much as a warrior can be at lower lvls ), good at aoe lvling.