First is the exceptionally high Charisma requirement in the original class. As Stuart points out, creating a really tempting class and then making it statistically unlikely that anyone will be able to play that class is an invitation to tinkering with the "3d6 in order" standard. In addition, I personally have a problem with ability score minimums; I prefer allowing anyone to enter any class at any time and simply penalize experience for those with suboptimal scores.
Second is the oddities of the way the class was originally presented. As others have pointed out, the wording suggests that paladinhood is not a true class, but a state layered onto the fighter class: "certain lawful fighters may opt to become paladins ... Charisma scores of 17 or greater by fighters indicate the possibility of paladin status IF THEY ARE LAWFUL from the commencement of play for that character." (Greyhawk, pages 4 and 8, italics added, but all-caps are in the original.) There's no suggestion that a Lawful fighter can't become a paladin at any point, without needing to switch classes. This takes a little of the bite out of the high Charisma requirement, because it's theoretically possible for a character's Charisma to increase.
Stuart lowers the Charisma requirement, as did I (a little) when I was toying around with paladins without spells. But a better approach might be to use these two restrictions:
- the earned experience modifier is based on the lowest of Strength, Wisdom, or Charisma;
- this prime ability is treated as one level lower on the ability chart for the purpose of experience (High Charisma becomes Normal Charisma, Low Charisma becomes Very Low.
Thus, opting to become a paladin means you have to work harder than if you stayed a mere fighter. Additionally, I like Stuart's alignment-based experience a little bit; I'd simplify it to "paladins only earn experience from Chaotic monsters and their treasure." A bit more restrictive, but we could do away with the restrictions on how much treasure a paladin can accumulate and just say that paladins only earn their bonus experience when they donate treasure of equal or greater value at a chapel or shrine.
I'm also good with offloading paladin powers to other things. For example, I would make the Detect Evil/Dispel Evil abilities into a feature of a holy sword, and make a paladin's horse into a quest object that any lawful character can potentially seek. Paladin curative and turning abilities could be invested in holy water: give all lawful characters the ability to turn undead or heal as a 0-level cleric, and simply give paladins a bonus equal to level-1.
That leaves paladins with only two inherent abilities: the saving throw bonus and immunity to disease. That seems doable, for a sub-class that has the same experience requirements as an ordinary fighter.