The suggested rogue/paladin multiclass feat from Complete Adventurer is certainly a good idea, as is giving him some appropriate assassin or ranger spells. You might also simply allow him to replace his heavier armor proficiencies for a monk-like level-based AC bonus and Charisma to AC.
Cityscape Web Enhancement lets you replace Ride with Tumble as a class skill, along with a couple others (Handle Animal for... Gather Information, I think?).
Charging Smite (PHBII) might be more appropriate than a special mount.
If he's got good Balance, Jump, and Tumble as a paladin for whatever reason, remains lawful, and keeps his spells, he can take Blade Dancer (Edit: Maybe that was Bladesinger. Bladesomething.) from Oriental Adventures. Acrobatics bonuses, speed boosts, benefits for attacking from swinging on ropes or other thematically appropriate maneuvers, all sorts of fun stuff.