If you take away cleric spells and switch to a prayer-and-miracle system, presumably paladins will be changed to match. I like the basic paladin concept, because holy knights are pretty standard in legend and fantasy. But I don't really like the AD&D paladin, because the class seems to be pretty just a "power bundle". The Supplement I paladin is better, because the high-level spell use is missing, plus I like the idea of Lawful fighters being able to take the vows of paladinhood at any time; but there's still a power list as opposed to a single power with flexible usage. I'd rather just give them limited cleric ability, but dependent on a physical condition. So, here's my proposed stripped-down paladin.
A fighter with Very High Charisma who has remained Lawful can take a holy vow of poverty and service at any time, becoming a paladin. Paladins use the lowest of Strength, Wisdom, or Charisma as their prime ability score, for the purpose of earning bonus experience. In exchange for these limitations, the paladin can perform minor miracles as a cleric.
At the beginning of every day, a paladin must pray; the GM makes a reaction roll to test the paladin's current faith, with a Normal reaction meaning that the paladin receives +2 to saves and immunity to disease for that day. A paladin can also use holy water to heal or cure disease, in addition to the normal powers of holy water, as if the paladin were a cleric of Level-1, using the lowest level of either the paladin or the cleric who sanctified the holy water.
Paladin Lords may dedicate an altar or makeshift shrine, with a reaction roll determining a bonus or penalty to the holiness of the altar (Very Low reactions mean the altar is cursed.) Paladin Lords may sanctify water in a font at such an altar to make holy water, which can then be used as if it were blessed by a cleric of half the paladin's level.
(This paladin is in some ways more powerful -- no limit on the number of times per day for healing or cure disease, able to make holy water -- but all these powers, including the +2 save bonus, become more fickle, and the ability to work miracles is limited by the amount of holy water the paladin can make and carry. The fact that paladins below the level of Paladin Lord can't make their own holy water means that they are dependent on clerics for their powers, forcing them to seek out temples as part of their service. Plus, it's much more interesting to watch a player wonder whether a failed miracle means it's time for a holy quest...)