Well, I don't consider myself a great optimizer but lets face it, there's not a lot you can do with paladins. Two skill points per level, usually with Int as a dump stat and one feat every three levels - there's not a great deal to work with.

However, the one paladin character I do play is kind of a specialist 'turtle' paladin. At sixth level he has combat expertise (yeah, Int wasn't quite my dump stat - Dex was) and Imp combat expertise. He's scraped up enough to buy +1 full plate, uses a heavy shield and will often cast prot. from evil on himself. The idea is then to go into combat and fight defensively with full combat expertise. He's managed to get his AC up to 32 - which means he's very hard to hit but also doesn't do much damage.

Basically he assists the party by holding enemies until they can deal with them.