Please see above for how Religion can EASILY be fitted into the game (geez, don't you guys READ my posts

). To recap, though:
1) Religion and culture should still be linked as they were in civ3 (i.e. religious improvements and wonders should still generate culture-and happiness).
2) Religious and/or Cultural Great Leaders-can be used to boost your empires culture or, a la CtP, they can wander off to other empires to preach gloom and doom (thus decreasing happiness levels) or even to convert citizens/units to your religion and or philosophy.
3) The ability to have a state religion-in much the same way as you have a government. Religions should be BROAD not specific (i.e. Monotheism, Polytheism-not Islam/Christianity)
4) Your relations to other nations should, as was suggested above, be a factor of both your culture group AND your religion-at least in pre-nationalism eras. i.e. Two European Monotheisms will get on better than an Asian and European Monotheism, but the latter will get on better than a European Montheisnm and a European Polytheism!
5) Under certain government types, it should be possible to declare a 'Holy War', as opposed to a standard war, against a civ with a different religion and/or culture. Such wars have a better chance of being approved by your citizens and by other civs (if they are 'Related' to yours by religion and culture). In addition, there is a chance, each turn, of these aformentioned civs joining in your crusade.
6) If you change to a new religion, or refuse to change to one that has popular support, there is a chance of a 'Religious Schism'. This is like a Civil War, but one driven by religion and not government.
7) (i) After you 'discover' a new religion, there should be a chance, each turn, of one of your cities population 'Converting' to that faith. Converts will have, in the city screen, a symbol over them denoting their new faith. The spread of conversion should work, in some respects, like plague in C3C-with larger cities being most 'at risk' etc.
7) (ii) Converts can either increase the chance of cultural conversion to a neighbouring empire (if it shares the same religion as your converts!); cause your city(s) to break away and become independant (religious schism), or try and force you to change religions; break away, as settlers, to try and found a new civilization.
8) Religious Specialists (Clerics/Priests)-sort of a slightly more potent version of entertainers (increasing happiness) and reduces the chance of conversions in that city.
9) Prior to the Industrial Age, it should be possible to commit acts of 'Religious Espionage', these would take the form of religious 'propaganda', as a means of converting enemy citizens. You should be able to spark a Religious Schism, plant a church (spy

) in an enemy city and the like. Obviously these will cost money, and the chance of success should be, in some respect, dependant on your cultural strength vs. that of your enemy.
Just as a side-note, planting a church in an enemy city both makes it easier to commit 'religious espionage' and increases the chance of natural conversions to your faith (if applicable).
Anyway, this is a more succinct re-hash of what I've said above-and shows that, in my opinion, religion can be easily incorporated into the game.
Yours,
Aussie_Lurker.