Which would you prefer?

[Keebz]

I'd probably go paladin then, as you don't have to worry about the exp penalty shunning.

Warrior is fun too (I have 2 warriors), but you will have trouble keeping aggro, twinking is most of the fun and there's less buttons to press in general. Paladin will allow you to learn some of the spell lines and should keep you entertained all the way to 60 without raid gear.