I disagree: I am
very tired of seeing Justinian and Theodora as Byzantine leaders

Plus, it's no shame at all, you can find equally big (if not bigger) personalities in medieval Roman history in abundance. Justinian and Theodora are just more famous with mainstream audiences, which is partially why their history is accentuated.
Irene is not a particularly good choice for a leader imo. Being an integral part of politics and becoming a ruler are hardly good qualifications for including a leader to represent a civ. She is consequential, but in many ways for rather bad reasons, not just good ones. More importantly, there are better/more interesting choices for Byzantine leaders. If I compiled a personal top 10 list, Irene wouldn't even make it on there, frankly.
I am adamantly against making the Byzantines into a religious-focus civ (again). They never were religiously focused (not more so than their contemporaries, at least) and built a far more lasting reputation in diplomatic and cultural terms. Even a military-oriented Byzantine civ would make more sense, if the choice of leader is appropriate.
Other than that, I agree with most of the choices presented here. I don't support Constantine as a leader choice, and I'm very reluctant on Heraclius. I'd rather add John Komnenos and John Vatatzes instead.
It's not comparable to the Macedon situation. Macedon is contemporary of other Greek states and in itself was pretty much a Greek state. On the other hand, the only thing separating classical Rome from medieval Rome (Byzantium) is time. Evolution culturally, politically, militarily etc were natural for an empire that was over 1000 years old.
Phoenician Gold's point isn't wrong per se, Byzantium
is the Roman empire, it's just imprudent and sloppy to blob them with Rome as it exists in the game right now because it severely misrepresents it. This in turns goes back to the point I have made in the past, in that the current model of the Civ game design makes it impossible to represent fairly and extensively all the phases of a certain civ. India has already been mentioned, but even Germany counts in Civ VI, really. One could argue that other than the UU, Germany in Civ VI is basically the HRE rather than the state we'd definitively call "Germany", so that part of its history (Prussia, Kaiserreich etc) are completely omitted.