Warrior is both a tanking job and a DPS job. I wouldn't say that Paladin is both a tanking job and a healing job. They've really only got Holy Succor and that's it for healing others, Paladin is solely a tanking job and it does not excel at that.

By the same notion, if any job could heal better than a White Mage there would be an uproar. Why? Because the only thing that White Mage excels at is healing, that is its sole role. This is why there is a problem with Paladin and Warrior. The only thing Paladin can excel at is the tanking role and Warrior beats the pants off of it in the tanking role.

For Paladin to be useful, it must excel at the tanking role more so than any other job because that is all it is made to do. Paladin should, at the very least, be the safe tank. Warrior can be used as tank to kill things faster but it should not have higher overall survivability than Paladin.