The current state of warriors is that unless they have something to close distance, or you have a dedicated healer, you're pretty much bound by how much damage you can do in the shortest period of time possible.
With that beind said, I'd probably put Troll on top of the horde list of warriors, followed closely by Belf. Passive snare reduction from the troll helps a lot and when you pop your haste cooldown it has a significant boost to damage output and rage generation. Belf's silence helps for sure but it also gives you a small rage boost and allows for another ability to be used.
Goblin seemed like it would be good, but, the rocket jump just isn't that terrific for warriors.
Taurens are nice for carrying flags, so if that's what you want to do then that's cool.
Orc's are good for Arms builds. Just hope to get some lucky rng and kill your target before you get kited into the ground