Generally for paladin's I recommend single classing or only one level of paladin.
Their best abilities (turning---yes, even at -2, lay on hands--if you've got charisma, smite, and mount) all scale with levels and are all extremely useful. It's also one of the few classes that has Holy Sword on their spell list and that's going to take single classing to get to.
For the best paladin though, be a cleric who takes the hospitaler prestige class. If you take one level of paladin first or manage a level of contemplative and take the mysticism domain, you'll have all the perks of a paladin except you'll trade a mount for full spellcasting progression.
Note: Smite Evil is replaced by the first level R&R spell Smite which while it has it's limitations, it is also available as Smite Chaos, Smite Evil, Smite Law, or Smite Good as necessary to either alignment or foe.
But otherwise, I'd recommend staying single class paladin. Believe me, the first time you manage to get to melee with a lich, and instead of stabbing it, you Lay on Hands for (13th level x 10 charisma modifier) 130 points of damage to a creature with no con... Well, it feels good to incinerate a lich in your holy aura, let's just put it that way.
Edit: A single level or the full progression of Templar are also very good choices though there are significant trade-offs there. For one level you get specialization and mettle, mettle combined with a paladin's divine grace and a hopefully armor of command/cloak of charisma setup can have you saving against everything that requires a fortitude or will save as if you had evasion for those two saves, tack on a vest of resistance from tome and blood and you'll be an even bigger force for lich's to reckon with as you can shrug off many attacks. Add a ring of evasion and you'll be a complete Wolverine, always refusing to go down no matter what you get hit with.
If you keep going the full progression you'll get extra smites and damage reduction meaning not only will you shrug off spells, but a lot of the damage you take will be reduced too. Combine this with Shield Other from that cleric and well... There are very few characters with whom flesh wall is not only a requirement, but also an honor and a talent, but not only that, a role playing concept that fits well with a paladin's code.