The Paladin was added to D&D really early in the game's history - in Supplement I: Greyhawk at the same time the Thief class was introduced. While the idea of the Paladin, and later the Anti-Paladin is interesting and a part of the game's history... there was just so much wrong with it from the outset.
Having to be Lawful wasn't actually the problem (although certainly it was something many young, rebellious players bristled at) it was a few other things:
Requires a character have a 17 Charisma. Less than 2% of characters would qualify. This encourages "alternate" methods of creating characters, include outright cheating to get that 17.
Can't associate with non-Lawful characters. This is where the "Paladins are jerks" idea probably came from. In order to keep their Paladin character a player needs to try and enforce an alignment / behaviour choice on all the other characters in the party. Players in RPGs don't like being told what to do... and certainly not by another player.
They're just better than regular fighters. Why be a fighter when you get all sorts of extras for being a Paladin? That lead to "fixing" the fighter to balance it compared to the Paladin later on... and that one-up back and forth "fixing" continued for the next 30 years.
So let's take a fresh look at the Paladin (and Anti-Paladin) and in the same vein as our minimalist sub-class we did for the Bene Gesserit create something for B/X D&D.
Paladin (Anti-Paladin)Our new Paladin (and Anti-Paladin) isn't restricted from adventuring with other player's characters, even ones of other alignments. However due to their different experience point awards they may want to focus on different aspects of the adventure.
Fighter Sub-Class
Note: Bracketed text applies to Anti-Paladins
Restrictions
Must be Lawful (Chaotic)
Minimum Charisma score of 9
May not use ranged weapons - Bows, Crossbows, Slings etc.
Special Abilities
Save as Dwarf / Halfling
Immune to Diseases
Treat Lance as Polearm - d10 - while Paladin is mounted on a steed.
Cleric Spells Usable Once Per Day
Remove Fear (Fear) at 2nd level
Bless (Blight) at 5th level
Striking at 8th level
Cure (Cause) Serious Wounds at 11th level
Paladin Experience Points
Gains 0 XP from Lawful (Chaotic) Enemies
Gains 1/2 XP from Treasure
Gains x2 XP from Chaotic (Lawful) Enemies
I've removed the Warhorse, which felt like an expensive car you were always worried about parking in a bad neighbourhood while you went into the dungeon. In it's place is a more generically useful ability for a "mounted knight" that also rebalances D&D's weapon charts between Polearms and Lances.
The Clerical spells are steered away from the overtly magical until the Paladin gets to 11th level. Until then the effects of their "spells" could be seen more as their reassuring presence, rousing speeches, and martial training. Only the most devoted will reach the point where they can heal someone's wounds.
