A paladin is only a paladin if it's lawful good, period. That IS the archetype. Don't have alignment? Don't have paladins. If you want a special arbiter of chaotic neutral virtue then make it up and give it a name that ISN'T PALADIN!
I have to spread XP around first, but you nailed it.
A holy warrior in the service of a deity is a cleric.
A paladin is a champion of Lawful Good ideals. He might belong to a church, but his primary devotion is to Lawful Good.
There is nothing wrong with having some classes represent more tightly-defined concepts. This was the whole structure behind AD&D's sub-classes: fighters, clerics, magic-users, and thieves were broad enough in scope to represent many different character concepts. Rangers, paladins, illusionists, druids, and assassins all represented very specific character concepts (and other than the illusionist, some definition of their role in the world).
I think it's a mistake to elevate the "specialized" classes to the same level as the "general" classes and open them up to the same level of customization. They don't need it, and in doing so they lose their distinctiveness. DDN "themes" might actually be a better way of implementing these classes, but that's probably not going to happen, as people are attached to these actually being classes.
The AD&D paladin was very distinct from a fighter/cleric in its abilities, restrictions, and role in the game world. When you loosen up the alignment restrictions, de-emphasize alignment-related abilities, and call him a divine champion, the distinction between a paladin and a fighter/cleric starts to disappear.
Enabling each alignment to have a holy champion reeks of the "needless symmetry" that the 4e designers went on about. The ideals of Lawful Good are difficult to uphold, so it gets a special champion. Evil gets hordes of demons and devils. Chaotic Good is frankly a much easier code to live by than Lawful Good and requires much less personal sacrifice, so it doesn't get a special champion.
What is the difference between a druid and a cleric who worships nature in some way?
A cleric is an ordained member of a church, trained as a warrior and a scholar. He is granted divine spells by the deity (or deities) whom he serves (or by the deity's servants).
A druid is a protector of the natural world, trained by other druids outside of a formal, organized religion. Her spells are granted to her by her deep connection with nature itself. The trees, sun, and moon are her deities.
A cleric who serves a deity of nature most likely belongs to a less formal and rigid church, but ultimately still serves a deity and that deity's goals. A druid might acknowledge a nature deity, but her powers are still granted through her connection with nature.
Unless you play in the Forgotten Realms, in which druids do have to worship gods of nature. In that case, the distinction is pretty muddy.