The speed of conversion can vary greatly based on map type, map size, and the religious beliefs you chose; some beliefs allow you to get cheaper missionaries, quicker Great Prophets, or to have religion spread on its own faster and farther than normal. It can also vary depending on if an enemy AI is playing religiously itself.
I'd expect conversion to be easy on Pangea, and, in a game I just finished, I had almost all three other Civs on a Standard-size map (I like a little extra room, so I play standard map size and take out a few civs and CSs) following my religion by 1000 AD.
If the enemy AI is playing religiously-based strategy, expect it to be harder to convert. On the other hand, if they all go for war-mongering, they'll sometimes be a cake-walk. In the same game I already mentioned, Greece didn't found it's Pantheon belief until fairly late, around 0 AD. And that was a Standard speed game.
In short, it all depends.