I think paladins are pretty great but they're kind of way too tight with their spells - as in I feel like you do not have the diversity nor the wiggle room to choose. If we compare them to their other 0-4 spell level buddies - Ranger lets you choose from the book a good pool and Harbinger gets both lots of choices but also many spells and they can even in some ways be a caster.
It is not really a weakness by any means but it means paladins, even with their oaths, end up being very samey. So my idea is this-
Core book - I think they should get Shield of Faith and Magic Vestment. Haste I think is reasonable as Harbinger also has it. You could probably stop there after giving Paladin more choices with just those independent of the next part of my idea.
* Give Paladins access to the cleric domain list - prune non-applicable ones from choices - such as the explicitly evil ones, ones concerning alignment.
* Assign each level a spell thats part of the paladin spellbook (but normally not choose able) to those remaining domains.
* You now get the flavor of that domain (maybe tailored to the paladin experience) AND a free spell 1-4 tied to the theme of said domain.
With the whole idea between your oath and your domain you can truly begin to resemble a champion of your specific deity and a specific cause. You can be a paladin of Kossuth with the Fire Domain, or Lathander with the Sun, and so on.