I should qualify myself a little by saying that I'm a game maker, not a paladin fanboy!
The Paladin seems deeply weak when compared to the to the Champion. The Champion enjoys favorable spell level breaks, (like Death Ward at 7th, rather than 9th) gains many more spells, and yet retains the same attack bonuses and raw saves. I'm not convinced that a +2 to saves (and a potential +2 more to fear saves) is worth the cost.
Whilst on the topic of the Paladin, Holy Shield, while cool, is an odd saddle to put on the class. It essentially forces a sword and board style with the class, but, due to their somatic spells, forces a Sword and Small Board style. D&D has often discouraged certain armaments with class abilities, but it hasn't (and shouldn't have) forced certain equipment types. I think this ability, while cool, needs to be reconsidered to allow for broader character choices. Alternatively, Paladins might be the only class allowed to cast somatic spells with all shields, like a free still spell effect. That actually might go part of the way toward equalizing them with the Champion.
The movement away from a Charisma-focused Divine Grace makes the Smite Evil's reliance on Charisma stick out poorly. The Paladin still requires a high score in Charisma to use their single strongest ability-- but the fringe benefits of that score- Turning and Saves- are lost.
Though Immunity to Fear is a weird thing for a character to have (it makes them like holy psychopaths), it's removal wasn't replaced with anything. It's strange to see the Fighter gain something like 25-30 feats added to their class abilities when compared to SRD while the Paladin has only lost abilities or had them weakened.
Pierre, did a Paladin hurt you in the past? Show me on the doll where the Paladin smited you.