I make the following changes to the paladin for my campaign:
Paladin (pp42-45 PH)
[/i]Divine Grace (Su):[/i] Divine grace works differently to that described in PH. At 2nd level, a paladin gains a bonus equal to her Charisma bonus (if any) on saving throws of one type (Fortitude, Reflex or Will) of her choice. At 7th level, she gains a similar bonus to saving throws of another type (different to that chosen at 2nd level), and at 13th level she gains her Charisma bonus to saving throws of the third type.
Special Mount (Sp): Paladins do not gain the Special Mount class ability (although they can take the Leadership feat to acquire a cohort which can be used as a mount).
Domain Spells: A paladin must choose one domain from the list of domains available to the deity she worships. Like a cleric, she gains a bonus spell slot for every spell level she is able to cast (starting when she can cast “0” spells of that level), which can only be used to prepare her domain spell at that level. Unlike a cleric, she does not gain any domain special abilities from choosing a domain.
Bonus Feat: At 5th level and every five levels thereafter (10th, 15th, 20th) a paladin gains a bonus feat. This bonus feat must be a divine feat (see Chapter 3 Complete Divine and Chapter 3 Complete Warrior – feat still subject to DM’s approval), Extra Turning, Improved Smiting (p82 Complete Divine) or Improved Turning.
Weapon Specialisation: From 12th level, a paladin can take the Weapon Specialisation feat if she otherwise qualifies for it.
The effects of the changes are to enhance flexibility in the paladin core class (it's no longer bound to the mounted knight paradigm), and to encourage players to keep taking paladin levels.
Cheers, Al'Kehar