I play almost exclusively on Deity Standard size maps (few early games on Immortal & Emperor) and the only time that a civ even came close to a religious victory was a game where I was going the domination route - Scythia had converted 5 of 7 civilizations (the 8th, Gandhi (who plays a heavy religion game and was their neighbor) I had killed in the early game) and I purposefully wiped them completely off the map to ensure that my later conquests didn't flip a civilization over to them by nature of the conquered civ going to 1 city or something. In fact, now that I think of it, the only reason they went up to 5 of 7 civilizations was because I knocked two civ's that had founded religions down to 2 cities or so. So it was my warmongering that indirectly lead them to a near-religion win. I've also never even built so much as a single holy site in any of my deity games, except ones where I was playtesting ways to found a religion against the deity AI's.
I'm sure given the right circumstances, there are other games where a civ could have gotten close, but I've had totally peaceful, no war Deity games where I won with culture or science that religion never got close. On island plates it's almost certainly improbable for the AI to win religion, Pangaea seems too packed in for a single civ to gain much ground (haven't seen more than 2-3 civ's converted), Fractal seems to be too terrain unfriendly for the civ's to get much religion spread (again most 2-3 cities), Inland Sea the civ's are too spread out and logistics are too complicated going through neighbors (have only seen 1-2 civs converted in this map), and Continents map seems the most likely for some AI to get close on religion (it was on continents that I had the game where 5 of 7 remaining civs got converted, and I had a few other games where it was 3-4 civ's of 8 converted). Likely the fact that on continents they can send apostles from any direction to the other continent and on their home continent they only have a couple civ's to compete with, so they can snowball a bit. Generally if you have 7-9 cities it's kind of tough for the AI to get any kind of religion into your territory. Most games I play I don't even get a majority religion in my civilization at all. Heck, I feel like I'm lucky to get one or two converted cities.
On a small or tiny map (which I've played on neither), I could see how it could be easier for a dominant religion to form and the AI to win that way, but the same can be said for cultural victory as well - or any victory because of less competition and smaller spaces with less cities to work with. Arguably the only victory that becomes harder on small and tiny maps is Science because as far as I know production costs remain the same.
If you wanted a peaceful way to absolutely prevent an AI from spreading their religion to you, without going to war and without founding a religion, you could always just build 6 scouts (6 turns) and have them sleep on the adjacent tiles around a couple of your cities (that'd be the lazy way, most of the time you could just move them around to block the apostle from moving). An even better way would be for them to be actual military units (to have your military defense boosted) in the same formation. This would prevent apostles and missionaries and any other enemy unit from moving next to your city to spread religion. Even another way would be (an emergency situation, because it'd be expensive), if you had a city with any other religion at all, you could build an apostle, launch an inquisition and just have one or two inquisitors to eliminate religion spread in the majority of your cities.
I hate to say it, but it sounds like if religion is a true threat to you losing the game on higher difficulty levels, even if you're not going on the offensive and conquering anybody, it's probably your tactical error that caused the victory. I don't mean that trolly at all or as an insult, so please don't take it that way. I'm just saying that, usually it's difficult for the AI to win anything, even at higher difficulties because they simply don't handle districts well and they don't handle war well, they don't even handle efficient religion spreading well other than carpet of doom, the only cases where they win is if their built-in bonuses let them run away from the game (e.g. you didn't built enough infrastructure (or conquer enough infrastructure) to make up for the difference.
