The problem isn't the UA, or even the UU's, it's their timing. They should be medieval. As ancient/classical units you don't get to build them cos you're spending your time focusing on religion (or you're not, which is why you don't rate the UA). Dromon could easily be a kickass galleas (even if I'd lament the loss of ancient naval ranged). The cataphract feels right as a horseman, but could probably survive light historical scrutiny as a knight instead.
If the units were medieval this'd actually provide good synergy cos you can set up your religion base, then use your UU's in the medieval to carve the dense wide low pop empire that's required to spread religion super fast.
I think this is right on the money here. The dromon being ancient era and the cataphract being classical era makes it difficult to take advantage of all of Theodora's abilities. She has no innate ability to generate faith, which means either you're lucky (nearby religious state, nearby faith wonder, etc), or you have to really work at creating your religion.
There would be nothing wrong with this if it weren't for having such early units. While they are very good units, it's very difficult to use them if you're so focused at creating and spreading your religion. This is even more true on the higher difficulties. If the Dromon and Cataphract replaced the Galleass and the Knight, then you'd have time to make use of them. By then your religion will have been set up and spreading.
In my experience I either focus all on Religion in order to select good beliefs before they're all taken, or I focus on her units and make war. It's very hard to do both; do any other Civs have this issue? Compare to the Celts who are all but guaranteed to not only get the first pantheon, but have a great shot at the first religion; they get free faith just for being near forests, no buildings required. And one of their units earns faith on kills. Byzantium may have one more belief, but what's the point if it isn't that great-- compared to the Celts who almost all the time can get exactly what they want, first.
Part of the problem is how fast even non-religious civilizations are able to found a Religion on Immortal. Not only do they have faster faith generation, start with free techs, build faster, but the more pantheons are founded the more yours will cost (and set you back more because you lose all that faith). And then when you finally get to found a religion, you're lucky if there's anything left that's even that useful to you.
Another problem is that Theodora's units and abilities are good, so buffs like giving her an early Great Prophet at Theology is probably too much. While her individual abilities and units are great, there's really no synergy at all between any of it. She may get a free belief of her choosing, but she has no boost to actually getting there and making sure she chooses something nice (and thus getting stuck with a poor unique ability). And her unique units have nothing to do with her UA either, and both come very early and directly clash with your ability to create a religion quickly.
So Theodora has a hodgepodge of nice stuff none of which work together at all.