Gehennas
Warlord
Don't know if I was just lucky (yes, there was some luck involved - I had a natural wonder nearby) but religious victory with Poland on Emperor (large map) was the easiest one for me. Also, the most boring one.
Pick a civ with religious synergy (not Spain!). Pick pilgrimage and mosques as beliefs. Build holy site in every city. Move your apostles in groups to quickly deal with enemy apostles. Never spend the last charge of Debater apostles. Always keep the Prozelytizers for the large enemy cities. I think that's all. You can also build some religious wonders but that's not neccessary. Most likely you will be behind in culture/science, but you should win before this lag becomes problematic.
Pick a civ with religious synergy (not Spain!). Pick pilgrimage and mosques as beliefs. Build holy site in every city. Move your apostles in groups to quickly deal with enemy apostles. Never spend the last charge of Debater apostles. Always keep the Prozelytizers for the large enemy cities. I think that's all. You can also build some religious wonders but that's not neccessary. Most likely you will be behind in culture/science, but you should win before this lag becomes problematic.