This sounds like a really good idea and reading about the AI-played games, it seems like it works also. Great job.
One thing though, I don't think that the AI realizes that there is a race to get the first great prophet out so that it can found a religion. The human player clearly realizes this and will prioritize the construction of the first pagan temple and the assigning of the first priest. After that, the human player will probably not bother with pagan temples and priests except when the happiness bonus or culture boost of the temple is useful. This is a clear advantage for the human player in comparison to the AI. At the highest difficulty levels, it can be a daunting task to found a religion in the vanilla game. But I don't think that it will be as difficult in this mod. We can of course solve this by playing at higher difficulty levels, but giving the AI all kinds of bonuses is not very elegant.
I was thinking of another way that was maybe easier for the AI to compete with the human player. Maybe, you'll like it.
What if the construction of say 3 pagan temples allowed the construction of a new small wonder, the Great Temple, that produced 2 free priest specialists. At the same time, the pagan temples ability of assigning priest specialists would be removed (reducing the value and thus the cost of these temples a little). In this way, there are still a lot of resources needed to get a religion because the construction of the three temples and especially the construction of the Great Temple would cost a lot of resources. But on the other hand, the race to obtain a religion between the human and the AI is probably a bit more fair. I think that the AI will go for such a small wonder, while not understanding the connection with obtaining a religion. The Great Temple should of course get a very high religion value for the AI, so that it will build it as soon as possible (like a human would). With the production bonuses that the AI gets at the higher difficulty levels, it will be a challenge again to found a religion.
Some details: If possible, the Great Temple could transform into the religious shrine for a specific religion when it is founded. The nations that fail on the race for the religions, will still have a Great Temple. That's not as good as the shrine of a religion, but still nice.
There will probably be more variation in the time needed to build the Great Temple between the various nations. So maybe that difference in founding time of religions that you were looking for will be present in the game in a natural way.