For Africa (Ethiopia) this church should be in:
They might be a bit later than the starting date, but their importance as the African Jerusalem was massive for the Orthodox Christians. Maybe it is a solution to allow them to be constructed.
Bonus could be, +2% converting of the population, +10% happiness (forgot the exact ingame term) and a increase intrade (due to a pilgrim industry)
Also this in modern Turkey should be worth a look: