Being able to build a temple to one religion or another would be interesting... I mean you build a temple to the Sovereign and that cancels out the ability to build a temple to one of several other god figures... but might have it own benefits to morale of your citizens - you get to choice what religion, if any, your kingdom follows by building a certain sort of temple. (or making a choice pre-game in character development)
At a diplomatic level other cultures who followed the same faith. Such as the Titan or Goddess of the sea, might be more friendly to each other. While they would also be more unfriendly to rival religions.
I also think that one of the key things that elemental is missing is racial and religious buildings and units.
The game is great - but at the moment, and as a beta i would expect little else, all the civilizations are basically the same.
which makes for good game balance - but less fun IMO
I'd love to see a faction system - be it racial - or religious - or better yet BOTH.
I mean having three other sovereigns form an alliance because they all worship the goddess of the moon and set out to destroy you because your kingdom worships the moons goddesses hated enemy her brother the sun God would be interesting. As would having a bunch of goblins civilizations team up to destroy you because you were playing an elf... but that's a topic for another thread.
I personally think you would need a very defined group of Titans - Gods whatever - that was fantasy based and had positives and negative relations with all the other Titans - Gods etc in the mythos...so you choose your kingdoms religion in game in some way and reaps the rewards or suffer the consequences to some small extent. I say small extent because it's only a tiny factor in a game with many aspects - but i think it would add an interesting factor to diplomacy.
Conversion - could become another way to achieve victory - though it would be a lot of work to work out how to implement it. i mean if you could convert the whole world to your religion you win. Bit like a diplomatic victory buy probably a whole lot more bloody if world history is any indicator...
Religious buildings and unit abilities could add a lot of flavor to the game... for example - worship the goddess of healing and be able to buy the ability to use a healing spells in the unit training area... God of war and get some civilization bonus for free at the start of game... etc.