My Suggestion for a change is easy. Add a job-trait, Auto-Regen, (and maybe Auto-Regen II), that will allow the Paladin to recover HP without needing to expend MP. An increase of DEF would be great as well.

I view Paladins as "Arcane Defenders" so they should be bad-ass damage takers (tanks), whereas Wars should be more Damage Dealers; but, as I see it right now, Paladins are gimped, and I can say that having my only 50 at this time being one. Nobody wants them for parties. :-\