I find it strange religious victories have always been my fastest. Just remember to use both apostle and missionary to save yourselves alot of faith. Use your apostle to turn a city into non nonreligious city then use missionaries to covert it the rest of the way. Always use missionaries on cities without religion. Save your apostles last charge to combat other religious units. Faith and production are the most important things earthen goddess is the best pantheon and will give you tons of faith.