I can agree that Paladin is in a strange spot right now. It simply has too many situational moves and as many holes in its ability repertoire.

I say change the whole thing. Take the past Paladins from the Tactics games, Cecil, Beatrix and let them be the base and mold something simple and impregnable, like it was made to be.

Give it a natural cure ability that can be cast more than just 3 times since Clemency MP cost is insane. Let them cross-class Esuna. Chance Flash for Arch Sword that does AoE damage around the person and create enmity. Change tempered will for something that lets close the gap between you and the target. There is a lot of possibility here, something can indeed be done with Paladin for next expansion.