1. Take Naberius, Divine Might, Divine Shield, and Hellreaver. Houserule that all swift action 'paladin things' can be activated as a single swift action. Include Battle Blessing. Be the ball - the best ball.
2.
http://www.giantitp.com/forums/showthread.php?123630-3-X-Person-Man-s-Guide-to-Shields - dip fighter for moar feats, be captain america.
3. Freakin' Battle Blessing, man. Plus a wand gauntlet or something. Cure light wounds as a swift action really ain't that bad. There's also some attackey paladin spells in Spell Compendium from memory, being a Justice Power Ranger isn't a terrible use of time.
4. Charging Smite and pounce. Just.. do it.
5. Rhino's Rush + Charging Smite and pounce is good times.
6. Iaijutsu Master +Iaijutsu is a very interesting kind of paladin to play.
7. Pocket cleric. Pocket sorcerer... ehhhh. Pocket cleric? Thematic! Have the cleric be yoda, and never explain why he is in your backpack.
8. Battle jump and pounce. Suddenly, your shit is not quite so terrible because double damage is.. double damage.
9. Luminous Armour sounds like a better idea than full plate, especially if you're rocking a monk's belt or a decisive strike monk dip combined with ascetic mage (ascetic knight? or just a good wis).
10. Spam diplomacy. Paladins are also faces, sorta, so spamming diplo on everything can also be their job.