Byzantium pretty much has to invest heavily in faith early to actually get a religion in order to use its power. So that involves one of the following:
1)Getting a faith-producing pantheon, which requires you to build a shrine ASAP, to actually be able to take advantage of one of them, and to actually get it.
2) Build Stonehenge, which becomes increasingly difficult as you go up difficulty levels. On Emperor, at least, it requires a capital with at least decent hammer potential(including a few forests for chopping) and prioritizing teching to Calendar(which, depending on your start, may be an entirely useless tech in the near-term other than unlocking Stonehenge). You'll probably still need to build a shrine if you want an early pantheon
3) Luck into being near a faith-generating natural wonder, or any natural wonder and manage to get One With Nature(which isn't a high-priority belief)
4) Build the Hagia Sophia. Of course, this requires getting to Theology relatively quickly and actually building the wonder, which isn't anything to write home about other than the free prophet. You'll likely be founding one of the last religions if you manage to build it.
5) Get a free great prophet from completing the Liberty policy tree.
Liberty may not even be your best policy option, and then there's the opportunity cost of taking a prophet instead of an engineer or scientist. Alternatively, you could take a GE and rush-build the Hagia Sophia.
However, the AI doesn't seem to value tithe or itinerant preachers very highly, so it's actually decently likely they'll both still be available if you found a religion late. You're likely to miss out on many of the better follower beliefs though.