I think we can agree that the AI in Civ V is not a strong point.
For sure!
A broken UA is more of a factor when playing a Civ though.
Quite true. I think we can all agreed that, because you were playing a totally random setup and rolled a great plains map, not being able to exploit a water-based UU/UB/UA would make the game less enjoyable. (Setting yourself up for a challenge is different.)
Fixing things from an AI perspective seems a distraction in this context.
I could not disagree more. This one detail is objectively and unambiguously broken from an AI perspective. Any fix that corrects this particular defect for the AI will almost certainly fix things for a weak human player (at any level) as well as the strong human player using Theodora at Immortal or Deity.
How would it be implemented that Byz would always get a religion? Would they get it automatically such as when a tech was researched? Which tech? Too early and it will get a religion first, too late and it will reward lazy gameplay as you would be guaranteed a religion. If it was based on a palace yield or a unique specialist that could be worked it would allow Byz to get the first as well as the most powerful religion.
You raise very legitimate concerns. I would love to see the discussion focused on specifics mechanics to fix the problem without being OP.
There are other UA abilities that the AI just does not handle well...
I submit for your consideration that there is huge difference between the AI not handling certain civ UA abilities well and, for all intents and purposes, a particular civ not having a UA at all.