My personal feeling on the base class/PrC issue is that a good base class must be at least three of the following:
1) Based on an indefinitely-scaling concept. "I'm a consummate scoundrel" (rogue) scales indefinitely, for instance, since hiding from people and tricking people is always as powerful as the attacks you're hiding from and the things you're convincing people to do on your behalf; "I'm Errol Flynn" (swashbuckler) does not, since the concept of the acrobatic guy with a rapier hits a ceiling at some point.
2) Sufficiently broad to support multiple characters. The wizard concept of "I'm a smart, Always Prepared magic-user" can be narrowed down to "I'm a smart, Always Prepared mind-controller" or "I'm a smart, Always Prepared pyromaniac" or the like and still support a character; the fighter as it stands really can't do that, because "swords guy" vs. "tripper" vs. "charger" is enough to be a fighting style but not a character concept.
3) Different enough from other classes conceptually. The AD&D druid wouldn't have made a good class, since it was "as cleric, except XYZ" and was more of an ACF than a class, but it was differentiated from the cleric in 3e enough to be worth a full class.
3) Different enough from other classes mechanically. The samurai is different enough from a fighter
conceptually to be a different class, but mechanically the 3e samurai is nothing more than a focused fighter.
If a class meets 1/2/3 but not 4 like the wu jen, it can still be a good base class if you can use the same basic magic mechanics and still get quite different classes. If a class meets 2/3/4 but not 1 like the knight, it can still be a good base class if it's actually as different from others as 2/3/4 imply since you can probably find enough for it to do for 20 levels. If a class meets 1/3/4 but not 2 like the binder, it can still be a good base class if the one character concept the class does is done well and broadly enough. If a class meets 1/2/4 but not 3 like the 3.0 sorcerer was before it got the heritage treatment in 3.5, it can still be a good base class if the different mechanics are enough reason to use it.
Those criteria are necessary but not sufficient to make good base classes, though: classes that don't meet point 1 probably work better as low-level ACFs, classes that don't meet point 2 probably work better as a PrC, and classes that don't meet point 3 and/or 4 can probably be folded into another class.
So, to weigh in on the paladin as class vs. cleric specialization concept:
On the paladin though: a Paladin is a Cleric with persist Detect Alignment. Sure, there's Smite and the special mount, and Divine Grace, but....is that enough for it to be its own base class? Even if all alignments were accepted? I submit that it would not be. Not only that, but the major class features happen after level 1 (mount, Lay on Hands, Divine Grace). the Detect Evil is a spell, Smite is a spell, Mount is a spell, Lay on Hands is a spell, etc. I think that the Paladin would be better off as a Cleric PrC, and the Cleric should get more Paladin-y things from the start. Namely, Smite Opposition, the Auras, and possibly Divine Grace-esque features. A Paladin should take that base and focus on the combat aspects, improving Smite, the Auras for combat, and martial skills. It should introduce the Mount as a signature class feature. Which will not be a new mechanic, do note. It is based off of summoning spells, which you could already do. As it is right now, the PrC is way to specific, and this will open up that whole "divine warrior" concept to the rest of the gods. Now, there are ways to make it better. EjoThims is my favorite, because it makes a new concept from the combination. There's the combat specialist, the Fighter, the Divine caster, the Cleric, and the divine combatant, the Paladin. Also: Crusader.
By my criteria above the paladin meets point 1 ("slayer of evil and protector of good" scales with the evil you face), but not 2 (even with the various ACFs, the paladin class is more of a build than a class), or 3 (there are several other martial/magical "divine combatant" classes), or 4 (as dman mentioned its class features are nothing really unique).
Now, to riff on Amechra's idea for pseudo-gestalt and blending progressions, what I think
would be a good base class would be a generic Divine Champion class that can encompass the paladin as well as the soulborn, divine mind, crusader, and a few related PrCs that are basically "the paladin, but more so." All of the class features from all of those would be selectable for much better differentiation, and you could choose two power progressions for more variety and synergy. Folding all of those together so that you can build a mount-focused divine mind, or a meldshaping crusader with auras, or a paladin with Mettle from Pious Templar and a fancy magical sword from Shining Blade of Heironeous and Delay Damage from the crusader, or the like would allow for one conceptually-strong but mechanically-varied class like the wizard with its specialties instead of a collection of several one-build classes.