My raiding main was a fury warrior ever since the MC days. In order to maximize DPS you need to get a little bit of splash damage where possible. Although they have drastically improved rage generation for fury warriors, it is still very possible to be rage starved on a highly armored boss who does not have any sort of splash damage. Because of that, I'd probably go with a rogue. Much of rogues damage comes from white damage which means that it's less important you hit the skills at the exactly correct time.

For pure melee groups I'd rank the following as the easiest/most powerful to the hardest/least powerful:

1.) DK
2.) Paladin
3.) Druid
4.) Rogue
5.) Warrior

I have no idea where enhancement shamans fit into the mix.