I usually suggest giving Ledarship as a bonus feat at 6th level, along with a bonus +2 to leadership for being a paladin, as a replacement for a mount. This works well because the cohort scales with level just like the mount. Besides, every self-respecting knight needs a squire!
Though I am intrigued by the idea of letting the paladin have access to one domain plus a extra domain slot at each level. Good for a more priestly focus.
Though I am intrigued by the idea of letting the paladin have access to one domain plus a extra domain slot at each level. Good for a more priestly focus.