I think Paladin lores would be an interesting addition, making them focus more on warrior (offensive) or cleric (defensive).
Choices could be something like:
Charge or Protective Shield, Bash or Cure Critical (they would retain cure serious), Dirt Kick or Protection, or something like that.
Maybe two or three choices spread out across levels like warrior lores. I suppose it could be entirely new skills as well, but I always saw paladins as a mix of warrior and cleric, and thought it would be neat if you could chose a focus in your career.
