Well, there's the Grey Guard from Complete Scoundrel, which is great if you're wanting to walk the line between good and evil.
Or you could do the Annointed Knight from Book of Exalted Deeds, for focusing more on melee combat and personal permanent buffs, though it doesn't say that Paladins can multiclass with it and still be able to advance as Pallys.
Then there's the Divine Crusader from the Complete Divine, with the same issue as the Annointed Knight.
There's also the Hospitaler, which really pumps up the Palladin's healing abilities, and does say that Paladins can advance as both Paladins and Hospitalers. Also from CD