As things stand most of the domains are useless, virtually every cleric, no matter what god is running around with at least one of the 5 or so domains that grant Stoneskin/Haste/Improved Invisibility. Most of the domains see no use, and I am not sure I even want to know how many clerics have domains that actually fit their god.
So how can we make the other domains useful? Well, we could go into an extensive and complicated system of swapping in and out spells until they are all eventually roughly equivalent in power, but given the near universal "must have" status of haste/imp invis, it'd probably boil down to giving every domain access to one or the other. Besides, if we rewrite the spell list for every domain that might get a bit confusing for newcomers.
But what if, we were to leave the domains more or less as they are and simply give small thematic bonuses for those who pick a domain that matches their god? So to go with the sailing idea that I mentioned at the start, Clerics of Umberlee/Valkur/Deep Sashelas get a hefty bonus to the sailing skill if they have the water or air domains. Do you reeeeealy want that stoneskin even tho your god doesn't fit any of the domains? Knock yourself out then, but if he did, you get a special "good rper" treat.
Considering each in turn...
Not all bonuses should apply to all gods that fit a domain although you could give multiple bonuses, You could, for example, give the free summoning stream to all deities that fit the water domain, then give bonus sailing to Ocean/River themed gods, and the Cold resistance to the others.Air Relatively useless if fun for thematic builds for storm related gods and smiting by lightning. Turn elementals ...
Bonus to sailing skill for Naval deities.
Free Lightning/Air elemental stream for Elemental air themed gods.
Bonus to climb for gods with a focus upon flying.
Animal Popular with summoners, early access to True Seeing, Pollymorph for RP shenanigans. I don't see a need to change it myself, although if all this is a little overpowered perhaps the summon bonus could be limited to clerics with nature gods.
Perhaps a bonus to Animal Empathy now this is open for all to take?
Death Gives a funky, if mostly useless, summon (Seriously would give anything for a shadow mastiff summoning theme...) Access to Phantasmal Killer (yay low DC double save death spell.... ) empowers harm and inflict spells. Dunno, probably balanced? Maaaybe give a slightly better empowered Harm (30%?) to death/necromancy related gods? (lets face it, with an undead summon, its the necromancy domain.)
Destruction Turn constructs (next to useless, even more so when over half the constructs on the server lack the construct race and thus do not get affected) and a couple of near useless spells.
Free damage bonus? Say +1 damage on attacks per 5 cleric levels with a deity related to strength (Bane, Kossuth, Llolth?)
Free Power Attack feat for gods related to mindless destruction? (Cyric, Talos, Garagos?)
Bonus damage to fixtures?
Earth Turn Elementals. Meh. Stoneskin and Energy Buffer are nice tho.
Bonus mining chance such as that with mining picks/gem hammers?
Access to the Earth stream?
Evil Turn outsiders, most have turn resistance, some pretty meh spells.
Honestly there are too many gods with too many themes to theme this one to them all. Maybe just take away the old spells and give them the same spells as good domain, since the planar binding spell is already themed.
Fire Turn elementals, some meh but thematic spells.
Bonus mining chance for smithing related gods?
Perhaps a reduced cost to smithing related god saves for smithing gods?
Free Fire stream for more elemental fire related deities.
Good Much the same as evil, except its spells are much more useful.
Healing Honestly? the empowered healing is pretty good, mostly for Healer path clerics but thats good enough I'd say.
Knowledge Knock is nice, but scrolls are cheap. True Seeing early/more slots is nice but not amazing.
Bonus to Lore skill for deities focused upon storing/spreading knowledge.
Bonus scry duration/reduced cooldown for deities focused upon divination
Cheaper god saves for alchemy/art crafting?
3 levels of cleric count as 1 bard level for bard song for music / entertainment deities
Magic Some interesting spells if not ground breaking.
Small bonus to caster level against dispells?
Small bonus to caster level when dispelling?
Slight reduction in cost for Dweomercrafting?
Plant Turn vermin... dunno maybe useful in the underdark? Barkskin is good, i mean the wands sell well at least.
Trackless Step when not wearing heavy armour for nature gods?
Bonus to healing skill?
Protection I hear the sanctuary is useful, the spells less so.
+1 AC for defensive themed war gods?
Five levels of cleric count as one level of PDK for their abilities (Still need the necessary levels to unlock the abilities) allowing a 25cleric 5 PDK to get full access to PDK abilities without gimping their casting/dispel mechanics. (Probably pretty OP this one.)
Strength Early access/more casts of divine power and stoneskin make this pretty tasty really.
Dunno if it needs anything added, can you boost carrying capacity slightly maybe?
Sun Good substitute for the missing Repose domain for death gods that hate undead. Improved Turning. Not sure how effective this gets Sunbeam is kinda fun I suppose.
Extra Turning for free?
Travel I mean, it gets Haste. Nuff said really.
Trickery Yeah, it gets Imp Invis. It realy doesn't need anything.
(that said, a bonus to hide/move silent/bluff would not go amiss for gods who actually fit the domain)
War Battle Mastery is a fun gimmick of limited use being 1 per rest. Aura of Vitality is nice with the spell focuses, and Cats can help if you want a dex cleric... masochist.
Battle Mastery gains a 10 minute cooldown if your god is actually a war god?
Bonus to leadership/Intimidate (Only for the buff/debuff abilities not election manipulation)
Bonus to leadership/Intimidate for election manipulation for deities with a political focus (Bane/Siamorph for example)
3 levels of cleric count as 1 bard level for bard song for "glory in battle" type deities (Garagos/Haela Brightaxe)
Water Turn elementals again. psh. Ice Storm is a fun thematic spell but not a must have spell.
Bonus to sailing for naval gods.
Free Water stream for elemental water themed gods.
10/- Cold resistance for winter themed gods.
In fact, the same domain granting different bonuses depending on which deity you worship would give incentive for players to try out different gods that they may have not considered or make it more interesting if you play chars with two very different gods with similar domains.
Bonuses to skills could be say +1 per 5 levels for cleric class skills? Useful, but not "I am unrivaled in my field bow before me mortals" level of op. For cross class it could be +1 per two levels, can not exceed the number of ranks you have in the skill. Thus making them effectively class skills.
Its a pretty big upheaval, the geniuses behind the scenes may already be working on something else for all i know, and even if they wanted to implement something like this it might take forever but hey. Float the idea, see what sticks.