Have you read through this, Impulse? The fluff text for the setting is awesome and it has lots of plot teasers for specific ruins around each of the city-states.
Some really cool character ideas too... like the Jazst Dancers (acrobatic gladiators that mix drama, comedy and combat together); and silt skimmer sailors and pirates; and feral halfling headhunters; and desert raiding sand elves; and the Veiled Alliance (a secret society of arcane magic-users who refuse to defile the land).
So many good ideas! And it definitely is helping me understand some of the real dangers of travelling in this wasteland (like drowning in SILT!).
Thanks for clarifying the God-King part... I was wondering if it was a Sorcerer-King or something else. Outside of worshipping the Sorcerer-Kings/Queens, Athas seems barren of any true gods, seems more focused on "primal powers", maybe a little like the faerie/fey court, but even more so on powerful elemental creatures that seem locked/bound to specific places in Athas.
If you want my suggestion for a city-state to start in, I'd say either:
1) Tyr (the city-state), if it is like how it is described in the $e book, where the sorcerer-king has actually been betrayed and killed by one of his templars.
2) Balic... the place seems like a real hub of activity, and it has a couple of cool ancient ruins which might be interesting.
3) Nibenay... again, lots of potential in this place... plus it's sort of close to all sorts of neat villages and ruins. Could be fun!
Just throwing it out there.

Ayrn