I must admit, at first I really liked the Byzantine for their strong religions and early UU's. But upon a second look they aren't that great. They really lack syngergy in their uniques.
Their Quinqemeres are absolutely powerful and will give you dominance over the seas for a long period of time, however cities quickly become so powerful you can't take them with the quins, giving them more of a supporting role, either as defensive or as escorts. The same goes for the Cataphracts, they will give you a huge advantage on the battlefields but wont help you much against the cities themself, meaning again they are there to support your catapults and other units that will actually take the cities. Dont get me wrong they are both powerful and will help you in early aggression. However since you really need to focus a lot of research and production in the early game to even have a chance of getting a religion, and lets face it, their UA is far stronger than their UU's. Doing any sort of rush would cost you dearly in the late game, even in so far as to nullify it completely if you never get to found a religion.
Worth noting is that cataphracts will, as other mounteded units, be countered by the ressource less and earlier available spearman, though not countered as hard as other horsemen units they are still no where near the strength of a swordsman. Maybe in multiplayer where the speed of mounted units is really needed they will shine more, but against the AI who can't figure out how to defend their ranged units anyway, you really don't need anything that speedy and voulnerable.
Also anyone else noticed that the Byzantine start doesn't favor horses? 4 out of my 5 games as the Byzantine have had a horseless start, instead they tend to favor a costal or a jungle start, which I find somewhat annoying.