From what we've seen it's not really hard to found a religion if you really want to. Build a shrine and a temple and wait until you have 200 faith. Considering there's only one civ that get's a religion earlier (Celts) the Byzantines aren't at a disadvantage really. It's not like you have to ignore every other aspect of the game in order to found a religion.
Also both of their UU come at a time when religions are already founded( late classical era or medieval era), so there is no reason why they shouldn't be capable of using them.
Also both of their UU come at a time when religions are already founded( late classical era or medieval era), so there is no reason why they shouldn't be capable of using them.