I'm a VERY experienced player of paladins, both role-playing and roll-playing.
Tactically, I assume this is what you want, Paladins should have Charisma, Constitution, Strength, Wisdom, Intelligence, Dexterity if they want to be the pinacle of Badass when they are at high levels.
Charisma: Does Everything at once for a Paladin. You know that, I know that. The biggest difference at high levels is the saving throws, whereas at low levels the simple fact that you have charisma is good.
Constitution: Paladins need it more than fighters, because they don't have the same offensive power. Most of the Paladin's best attacks are derived from charisma, spells, and situational modifiers like charging with a lance on a mount. HP will be more important to you then it is to the fighter, without a doubt. After level 10, having an 18 starting Con would give you at least 40 extra hit points, making the gap between you and the 14 con fighter about 20 points bigger.
Strength: It's actually optional to do a strength based paladin. You can, at mid levels, make up for the lack of it. You have methods to enhance your own abilities, unlike the fighter who instead has constant abilities. Holy Sword, for instance, is like having a +10 to strength on average, if your using a bastard sword. Much cheaper and more efficient. Smiting with your Charisma mod also helps, and never forget to smite when you need it.
Wisdom: Bonus spells. Spell DCs. Will Saves. All very important things you will enjoy the benefits of. Minimum score of about 14, maximum of 20 to start (aasimar or such). You won't reap much more from this ability unless your epic, and have extra spellcasting levels.
Intelligence: I say intelligence before dexterity because I take expertise sometimes as a Paladin. I will agree that ambidexterity, or at least dodge and mobility, are good reasons to take dex over intelligence, but I choose this way. Also, I like to be able to perform my knowledge: Religion checks with a bonus... since I like to know things. It's good to have the skill points, but there are ways to make up for many of them.
Dexterity: Slight AC and Save Bonus can be made up for. As noted about intelligence, dodge, mobility, and spring attack are good if your a bi-pedal paladin rather than a rider. Hasted you might even be able to move/smite/move/smite with spring attack.
My recommendations for abilities:
Str 14
Dex 13
Con 18
Int 13
Wis 14
Cha 18
or
Str 17 (Raise to 18 at level 8)
Dex 13
Con 16
Int 13
Wis 14
Cha 17 (raise to 18 at level 4)