Paladin was always a solid class, simply on the fact that they could tank (to an extent) and heal. They were also the best class in the game for killing undead, as I think priest and paladin turns worked exactly the same (though I could be mistaken I didn’t play either class very extensively) but paladins hit harder and had more hit points to tank them.
Whereas rogues and rangers are going to generally hunt living targets that they can snipe/backstab, paladin will probably spend most of his hunts killing undead, so perhaps we just want to cater paladins toward that end. They can already turn which is huge, but perhaps they get a small amount additional holy damage on their attacks against undead, that could be increased to a moderate amount of bonus holy damage when they pray.
I think before some of the follower bonuses for paladin were damage buffs, I believe Aalynor gave a damage bonus against undead, and erisar gave a damage bonus against living creatures. I’m not really sure what the other gods follower bonuses were. But perhaps just give all paladins that follow a bonus damage against undead as the main perk, but then their could also be some flavorful follower bonuses that did minor things for the individual gods.
I already mentioned this in a few other posts, but just wanted to reiterate it here on the paladin forums, is if you want to give paladins additional tanking stats I think making them shield oriented. If the shields now have a block value, the paladin could have a chance to double the effectiveness of his block, or block an attack completely due to their affinity for shields, which would function like a dodge as far as a mitagation stat. I would see paladins as more of a class to sport either two handers or sword and board, not really dual wielding, so I think emphasizing shields for them could be a good way to.
You could also give them if a shield slam, if you wanted a way for paladins to have another way to pull aggro aside from turn that only works on undead.