Paladins are easy, but i'm with you on the sentiment. I've a prot pally myself, used him to box throughout whole wotlk. But man do I regret now that I didn't roll a warrior. So leveling one up solo now; no way I'm going to box pve with a paladin. Making not so popular choices and doing what you feel like doing is above all most important to enjoy multiboxing.