One can get a fairly easy religious victory on Terra by exploiting the overcrowding on the "Old World".
Chances are you will start with three close neighbours. You need to be quick to start a religion, and then make sure that Itinerant Preachers is one of your beliefs. You will also want Moksha as an early governor. Watch for one of your neighbours starting their own religion, and if they do, snuff it out quickly by converting their holy city which won't be far away, so this is easier than on other map types.
Now you have four civs of your religion bunched together. This becomes a critical mass. Thanks to Itinerant Preachers, your religion will spread by itself to the other civs, none of which are all that far away, being confined to half the map area. You don't really have to do much. Send out apostles now and again, but don't use them to convert cities, just preach once and move on to the next. This gives each city you preach at a little nudge towards salvation, and they will convert from religious pressure all the sooner. The more cities converted, the more the pressure builds, and you will find yourself discovering AI cities that have already converted before you even knew they were there.
It's pretty much an effortless victory.