Founding a religion.
In order to found a religion, you need a Great Prophet. In order to get a Great Prophet you need Great Prophet points, faith won't help you unless you produce
tons of faith and can buy it with faith (like you buy any great person) because you won't have time to accumulate enough faith before every Great Prophet is already gone. By the time you have temples it's very likely that every Great Prophet is gone so they won't help you get a religion. Unlike most great persons there is a small amount of Great Prophets available in every game, not enough for every civilization to found their own religion so if you want to found you need to work on it early. There's a few different ways to get your Great Prophet, depending on your civ and the difficulty level they will be more or less reliable.
- Stonehenge as you already noticed gives you a free Great Prophet but on higher difficulties AIs tend to build it really early.
- Quickly expanding to a second city and building 2 holy sites and shrines gives you 4 Great Prophet points/turn. In 15 turns you'll get the 60 points required for an Ancient Era Great Prophet. If your playing with Rise and Fall expansion or on lower difficulty, it should be enough to get a religion. If you're playing vanilla on higher difficulty eras progress too fast and you'll probably have to grab a Classical or even Medieval Great Prophet for 120 or 240 points and it's likely some AIs will start producing 8-10 Great Prophet points per turn before you grab one and get ahead of you.
- Divine Spark pantheon belief gives +1 Great Prophet point per Holy Site (for a total of 2/HS) and really helps you get a religion even thought it doesn't help you spread it as it doesn't give you faith.
- If you have a civ with an early wildcard slot (Greece, Poland), rushing Mysticism for the +2 Great Prophet points card can put you ahead of the opposition.
- The most reliable way i found to ensure i get a Great Prophetis to get a Holy Site in my capital early, build a shrine and then run the prayer project once or twice. It will take 4-5 turns to complete it and each time you finish this project you get something like 15 Great Prophet points.
Founding requires some efforts and will leave the rest of your economy/army weaker so it's not necessarily something you should do all the time but if you really try to get a religion, it's usually possible at any difficulty but Deity. On Deity in Vanilla it as usually not possible and never worth the effort anyway unless you wanted to go for Religious victory yourself. Rise & Fall might have changed that but i still have to play a Deity game in R&F.
Religious victory.
A civilization wins a religious victory when their religion is the dominant religion of every civ. Depending how it was coded this could mean they have to convert more than 1/2 of your cities to their religion or just have their religion in more of your cities than any other religion. In the later case, and if your 3 religions were equally spread through your 15 core cities, Egypt would just have had to convert 6 of your small coastal cities to become dominant which is really easy to do.
The best way to protect yourself from a religious victory is to have your own religion. The second best way is to make someone else's religion your own. This means conquering their Holy City (you don't have to eliminate the civ, as long as the original founder doesn't control the Holy City, they are not eligible for religious victory, neither are you), then treat that religion as your own, spread it to your cities, defend it with debater Apostles. As long as i've defended my religion (founded or adopted), i've never seen an AI capable of converting me in the long term. They might convert a city or two but sooner (usually) or later, i'll get those back. Winning religious combat is the best way i've found of strengthening my religious presence even on Deity. If you don't have any religion then you have to hope a weak religion spread to your land and you can defend it or just let AIs fight each other in your land as some sort of religious no-man's land and try to win before they might do since even declaring war on the dominant civ won't prevent passive spread. Unfortunately while you can tell AIs to stop converting you (they usually promise and then break the promise), there's no diplomacy option to invite foreign missionaries to your lands. Plenty of times i did sign open border with the closest civ that had a religion i liked to try and have them convert my cities only to see them run past my lands an go fight over some random CS which was already following another religion.
