Other classes to compare it to-
Equalish
Swashbuckler
Soulknife
Knight
Soulborn
Strictly superior to the Soulknife and Knight. Swashbuckler is a strictly superior charger on foot than the Paladin, and can also support the party with mobility-based skills. Soulborn is strictly superior to the Paladin (funny thing to say, I know, but it's true).
I consider Soulborns to be flat out inerior to paladins, but I would like to hear why you think they are better.
Swashbucklers only make good chargers if you play against type, they are kind of finesse fighters, which to me means that they aren't going to be shock troopering all that often.
Swashbucklers can charge across difficult terrain, how is that not skillful? Power Attack is nigh-mandantory for every Swashbuckler since they're supposed to be a damage-dealing class, and Insightful Strike can be applied to a few two-handed weapons like the spiked chain and the courtblade.
As for Soulborns, the smite ability is plain better, the lack of Turn Undead is only somewhat troubling, since the Paladin doesn't make spectacular use of it, either. They have substantially less MAD than Paladins, both because they don't have Wis-based Spellcasting and can actually function semi-competently as skilled characters without a high Intelligence score. Further, starting at level 4 the Soulborn gains, as a class feature, access to soulmelds like Bluesteel Bracers (Initiative Bonus), Fearsome Mask (Gaze Attack), Mauling Gauntlets (Meldshaper's Improved Trip), Riding Bracers, Silvertongue Mask (two of the better skill soulmelds), and Thunderstep Boots (Possibly one of the better additions you can make to a charger, mounted or not). That said, Soulborns are Tier 5. They really don't do anything as well as classes like Warlocks, Hexblades, or Rangers.
Paladin might be better than these in a case by case basis. He can easily be better than a Hexblade, and due to Drizzt fanboys, the Ranger.
Paladin is geared toward mounted charging, Rangers are geared toward TWF 3/5ths of the time. Though Rangers get awesome spells, and skills to compensate.
He is easily not better than a Hexblade. Hexblades get familiars, and that familiar is better than all of the Paladin's class abilities put together, including the Mount. If a Hexblade wanted a special mount, he could grab a Hippogriff familiar and rock out HARD with a 100' fly speed at level 7.
Can you go into details on how the familer is better?
Sure. Better BAB, shared skill points (although the Hexblade's list obviously isn't that great), often an ability to speak (and therefore use magic items), and with Improved Familiar it gains the bonus that it can serve pretty much any purpose the Hexblade wants it to.
Paladins are also not better than the Ranger. The Ranger's Animal Companion, although kinda gimped relative to the Druid, is still at least as good as the Paladin's Mount. The Ranger also has, as you said, a battery of skill options from a very awesome list and also a strictly superior spell list. Combat Style helps ease any kind of feat crunch, especially given that the bonus Archery feats, Mounted Combat feat line, and animal companion all synergize together very well. If a Ranger player works with the DM and gets campaign-appropriate Favored Enemies, then the Ranger does become strictly superior to Paladins as well.
I think the Paladins Mount is better than the AC,
I'm using a quick straight comparison here.
12 HD heavy warhorse vs 9HD heavy horse. +10 Natural Armor vs 6. 4 Strength vs 3 Str/Dex. Bonus Tricks vs Intellegence. Spell resistance, share saving throws, command own kind, improved evasion vs Devotion, Multi Attack and evasion.
Like others have said, it doesn't have to be a horse. You could ride a dire wolf if you wanted, and aside from your own lance attack the Wolf adds a pretty vicious bite and might trip them as well.