My experience has been mixed.
I first played a game on the world size one smaller than standard, and on noble difficulty. I ended up on one end of a long continent with a Peak (impassable mountain) choke point, so it was some time until I met anyone else, and even then only 2 other civs. By the time I met others I had a solid lead in the game, particularly in technology, so religion seemed to play little role in my relations with other nations - because those relations didn't matter much. However, I was concerned about religion. I destroyed one civ that never liked me. I attacked another, made peace and we never fought again but between the attack and the religious difference he hated me forever after. Only ONE civ I made friends with early (I was Rome, he was America) was actually willing to trade regularly. For some reason the religious penalty wasn't enough to wipe out that one alliance.
For my next game I picked a standard world size, terra (is this the new pangaea? if so that was an accident - I thought it was "earthlike" or something). I also selected one difficulty level up from noble (prince?). I believe I met every other civ by about 2500-3000 BC. Fast - and we're all on one continent. Despite a fabulous starting location and perhaps being first to found my second city, Egypt managed to create a huge lead, and the land around me was quickly filled in by the #3 and #4 cities of several other civs.
This forced me to fight some wars to expand. I'm more of a builder, but I tried to view it as practice of the new military system. My wars were pretty successful - first agains the Japanese, and then the Germans. They are both no longer threats and I have more land and cities in a mostly-contiguous empire. I also picked up some nice resources including copper and iron along the way.
BUT now back to the point of the thread - religion! I've never been at war with Spain, or Egypt. I had open borders with both, which Spain canceled for no reason. Though I've met Greece, I've never seen a Greek city. NONE of these three will trade with me regularly. Only the leading civs had any techs I didn't have and the -4 "heathen religion" penalty has made is so they all dislike me. Doesn't matter that we've never had war. Some say I attacked their friends (didn't have much choice...) others say I trade with their enemies, but even the one that DOESN'T have any other modifiers still dislikes me because of my religion.
I find being unable to trade annoying and a severe impediment as I fell behind in tech as I pursued my war.
Things I've considered:
Converting - but I can't because the other nations have not spread their religions to my country. We have 2 apparently unpopular faiths on tap at the moment. I don't think there's a way for me to spread a religion I don't have.
Fighting more wars - Does the "you attacked us!" penalty ever go away? I can probably pursue a strategy of a series of limited wars, trying to weaken one opponent at a time, but this doesn't help position with other countries.
I am about 4 techs behind the 3 most advanced civs at this point - 1 of which is egypt with HUGE culture and a HUGE game score. The other is my equal in most respect. The third not far behind me. None of the 3 are very close, and so are difficult to fight.
I feel like I have few options when it comes to diplomacy, and that this lack of options is due to religions differences causing all other nations to dislike me too much. Perhaps I could convert to "no religion" - if that eliminates the penalty. I haven't checked yet. (Lack of options in a game is bad feature.)
I'm just not seeing a lot of options for pulling this game out. Maybe I'm not good enough for this difficulty level yet, but I was OK at Emperor on civ3, so I'm a bit surprised at the way this game is going. I just can't seem to grow and produce enough, even though I probably now have the most cities of any civ. I'll be very interested to see what the HECK Egypt was doing in the first 50 turns. I didn't think you could pop cities or settlers out of goodie huts any more (except on "chieftan" or tutorial or whatever it's called now).
Sorry to ramble, but I'm not enjoying the religious experience just yet... I'm trying to separate my "religious issues" from the fact that this particular game on this difficulty setting with this particular map happens to be hard for me. But my first instinct is "get allies! splinter the opposition!" but that seems impossible because of religion...
(suggestions welcome)