Well, I realise that we're quickly approaching the point of 'agree to disagree here.' since neither of us are able to fully grasp the others viewpoint well enough to concede (not that there's anything wrong). But, I'll give it a go once more.
Certainly the elements don't just 'grant spells,' right? So simply by their faith in the power of these elemental forces, they get spells from them
Actually, they do. Faith by itself is absolutely powerless. The elemental lords work as representatives of the plane in question and select individuals to carry out the fight between the planes themselves on Athas. The cleric-to-be oftentimes forms a pact with the elemental lords. The elemental lords though don't care about good and evil, or right and wrong. They only want the proliferation of their element. The size and power of each plane is mirrored by its abundance (or lack thereof) on Athas. Hence some elements are on the verge of extinction (such as the elemental plane of rain, and that of water) while others have grown in power tremendously (the plane of silt).
By the same token, why argue against its inclusion?
Sorry, but even those who are generally in favor (as seen here, as well as almost 3 years worth of debate on the topic over at the WOTC boards) of including the paladin agree that its probably best if altered. I'm not really against the paladin in general as much as I am against the copy pasted core class version of it. I've already tinkered the holy liberator, consecrated harrier, church inquisitor (each with highly altered flavor text) renamed simply liberator, harrier, and inquisitor respectively (though I've only gotten around to using the inquisitor).
The paladin's abilities themselves come from divine favor, something that there is none of on Athas. That means ditching most of the abilities that rely on that, leaving basically a fighter with morals. Restructure the abilities then to be fueled by psionics and you simply have a psychic warrior of sorts with a code of ethics attatched. Sorry, but most of the ways I can think of to work it (altered versions of the paly) could be more easily filled by other core classes that fit better. I'd be far more inclined to keep the code aspects as flavor than mechanicaly incorporated into the class. If a fighter wants to follow such a code, then by all means. If a PC wants to be heroic, I won't stop him. In a game though where a major theme is the debate over which is best, the needs of the few or the needs of the many, and where there is often a result of the ends justifying the means, a class that is based on such ideologies like honor, virtue, chivalry, etc cut more across the gain than I would allow.
The Tribal Protector: a warrior born with the ordained mission of protecting his Tribe and his people [snip for space]
A fine concept, for a fighter. Explain then where you can in this example (which I do like for a fighter mind you), the tribal protector gains spellcasting, the ability to heal others, becomes immune to disease, gains a special mount, etc.
These paladins are a secret society of holy warriors who've managed to tap into a source of divine power allowing them to use divine magic without swearing allegiance to a Dragon King.
Same question here. What divine source are you refering to? The closest thing to divine on Athas are the elemental planes and the lords there, and they're certainly not about holy crusades. People are nothing more than tools to them, to be used as such. Of course, its a fairly mutual view taken by the clerics too, many of which use the power gained by the elemental lords as a tool in their own agendas, rather than fanatic religeous worship (but all clerics are individuals, so there are some zealots among them who view it as religion). The Sorceror-King's were also in a way god-like, but there were not gods, not divine at all. A key aspect of their creation allowed them to 'tap' into the elemental planes and act as a channel for their templars to gain spells. Now, you could argue that lowly little mortals eventually learned also how to tap into this power, but that, IMO cheapens the SKs.
The Liberators: another secret society working in shadows within the city-states of the Dragon-Kings, these masked warriors hold themselves to a code which gives great value to freedom as the right of every sentient being, and thus seek to undo the rule of slavery
I've used the general idea of the holy liberator PrC (albeit quite altered in the end) for this very aspect. In fact, there's even a precedent for it in the game in the near mythical tribe of ex-slaves known as The Free. Of course, like all things of Athas, the myths that talk of a group of people who set slaves free where ever and when ever they can is bunk. The Free do release slaves, but they release them to die in the deserts as freemen, not as slaves laboring away their last breath. They don't do it out of nobility, but out of sheer hatred and revenge against their former masters in the cities to disrupt the slave trade itself. That some slaves manage to live long enough to tell about the tribe is a side effect.
They will risk their lives to save even a single slave from a cruel master's yoke, will perform extremly public acts of rebellious mockery against the rule or the Dragon-Kings, and damage the powerbase of the Templars through whatever means necessary. Then, once their mission of the day has been done, they retreat into the shadows, remove their disguises and escape Templar notice while they plan their next strike against the tyrants
Extremely public acts? They'd be dead in a day. Everyone would be against them, from the common citizens who fear the templar's inquisitions, to the other slaves who would hope that turning in the Liberator would at least get them a reduced work load.