I've always played Warrior. It's been my only class in over a year. I'm doing savage right now and honestly, I don't really see the difference when I'm paired with a Paladin or a Dark Knight. I've seen both good and bad ones, with some Paladins ending up with terrible damage, and some Dark Knights almost coming close to my own.

It's a hard call to make, though. I think the only people who can say anything are the healers, since a Paladin's utility has a direct effect on their abilities.