While being a spontaneous caster, the spells at (the primalist's) disposal would be affected by the environment they found themselves. A summon nature's ally type spell would draw a creature that would normally be found there. An entangle spell would simply not work in a desert or arctic setting. From a mechanical and playstyle point of view, the player character will have to be very thoughtful of the terrain they are in.
Ah, the TABLEMANCER! Does he get his own hardback?

I kid -- while this idea does have some pretty tall logistical hurdles to execution, I think it, and your divisions between mentalists and arcanists, are great ideas. I definitely come down with you on spell list specificity, I think -- one of the most important ways to differentiate classes with spell lists is that their spell lists should do things that support their archetype and not do things that do not support their archetype.
Personally, I'm glad to see somewhat of a return to (AD&D2-style specialty priests) with the new domains in Next and this would go a long way in establishing a clear cut line of demarcation between Paladins and all but the most martial of clerics.
I could not agree more!
If you see the old school mace and shield cleric as primarily a warrior, sure, I'll admit it isn't conceptually far from a paladin. But that isn't how I see it. It all comes down to one thing: Strength score. A traditional cleric wasn't focused on one. He didn't need it. He became defined as a priest, and only a warrior-priest if one chose to make him that way. On the other hand, a paladin is a warrior first, and usually not even a priest at all.
I am absolutely in agreement on this point; the Knights Templar and Hospitaler and other orders sponsored by the Church were said to be "twice-armored," meaning that both steel and their faith protected them, but the knights did not have any religious powers or responsibilities vested in them by that sponsorship.
Within the game, I definitely feel that the most important characteristic of a class archetype should be the way it plays, and your assessment of the importance of STR to the paladin vs. the cleric is exactly the sort of thing I mean, and the reason why I don't place it under the "cleric" banner.
...I don't place it under "fighter," either, but that's only because I don't see any reason why the paladin power suite can't be equally as easily applied to a rogue or mage. My thinking here was, why have one subclass (paladin), when you can have seven or eight class variants benefiting from the same feat track?
I think Cleric is too broad a term to say what the class really is. I mean for me, a Cleric is someone who worships a god, and uses the power that their god grants them for their god's beliefs.
I think that is very sound, but the question it raises is what does that look like on paper? I can think of half a dozen examples without really stopping to consider it, and they would all play vastly differently. I could easily reskin any of the seven or eight archetypes I've proposed such that they relied on a deity's power to achieve their class goals.
My point is not that all clerics are healers with a spell list -- only that all D&D Clerics are. Some compression is necessary to effect playability.