The upside to running a Paladin is you don't actually need a single cross-class skill. Most of the Warrior skills are mildly useful at best, almost meaningless at worst. Conversely, if you're running a Warrior you'll want most of Paladin's cross-class skills. I'm talking about Convalescence, Provoke and Flash.

Paladin has the best damage mitigation of the two jobs. The shield blocks an average 25% damage each time and kicks in fairly reliably at high levels. That's on top of your parry. Additionally they have Rampart and Sentinel, two skills which have a solid amount of damage reduction. They also have the best emergency skill out of the two - Hallowed Ground. Making them invulnerable to almost everything for 10 seconds. Sorry fellow WAR's, but Holmgang sucks.

The two-combo nature of WAR hurts as much as it helps in some cases. Since your DPS combo doesn't have aggro generation beyond the usual bonus granted by Defiance. That said, Warrior does at least have one DR skill which is on its own cooldown and doesn't deplete your wrath to activate called Vengeance. Also, bloodbath and overpower is a lot of fun to use.

As far as tanking goes, I think Paladin has a clear edge for most content. Warrior is still a very competent tank, but Paladin just has too much raw damage reduction to beat easily.