There is only one counter to Byzantium w/ Crusade

[Piranga]

Very nice Eagle. I just finished my first Byzantine game as well. However it was one of those games where most things went smoothly. I got the crusade belief. My nearest two neighbors, Rome and Egypt both found a religion, did a terrible job spreading it and fought against each other. I eliminated the Roman religion easily and that was the start of a religious victory steamroll. Declare war on Rome, taking cities and killing units easily. Killing units near Egypt helped me eradicate Cleo's religion and I didn't even slow down the Tagma's before sending them right into Egypt.

Controlling three religious capital cities (standard/immortal) and I just felt unstoppable after that.

 

[IsabelBraganca]

If your are playing SS mode, Vampires are good against Byzantine. Usually I can tell which city the AI will target first. One well placed encampment with a Victor with Embrasure given the city and encampment two strikes. Your two best ranged units inside the city and in the encampment. That's 6 shots per turn. The vampires can finish the enemy's units off, and every kill will make them stronger.

 

[Park Hyun]

Haven't tried them yet, but once I started thinking about it, it seemed like lots of civs had potentially good counters:

Korea - huge tech advantage. Strong defensive UU.
Sumeria - crushing early war.
Zulu - corps of cheap powerful anticav.
Mongols - anticav cav.
Eleanor - no way for Biz to hold on to anything.
Ethiopia - I had ridiculous amounts of faith with Grand Masters Chapel. I could just spam units endlessly.
Sweden - those UUs should stop tagmas.
Maya - high tech plus brutal archers.
Rome - web of forts backed by ranged units.

And so on. It seems like yes, Biz can steamroll you but most civs should have time to prepare and some advantage to soften the blow. Maybe I just haven't seen how OP they are.

 

[Siddharth Venkatesh]

The horseman rush is the scarier aspect of the civ. Lots of civs have ways to potentially counter them during the Tagma rush, though it is still hard, but dealing with Horseman that do full damage to cities is incredibly costly.

I think Korea's advantages will come in too late. If you're close to Byzantium as Korea, you're probably going to get rushed before Hwachas or tech advantage can really kick in. Sumeria and Zulu do counter fairly well. Mongols as well, but Mongols diplo advantages can be neutered by declaring on them the turn you meet them. Eleanor's loyalty bonuses don't matter if you take enough of her land.

Ethiopia can do stuff with Grand Master's Chapel but you're really vulnerable to Horses early since you rely so much on monumentality and tend to have lower production if you're spamming your churches. If you get to the point where you have the Chapel unlocked, you're good, especially if you have enough hills for defensive terrain.

Sweden can do something about Tagmas but nothing about an early Horseman push. Horseman doing full damage to cities is brutal in multiplayer. Maya counters reasonably well, both because the the Hulche does ok against Horses if the terrain is defensible and because your cities suck for everyone else so no one really wants to war you in the first place. Rome's legions seem like a solid early game counter, but as Rome, you have to be more worried about the Medieval push, as your advantages die out. If Rome can snowball sufficiently, they will be safe.

I never play 1v1 games in multiplayer, and your best bet in a free for all setting in which you are close to Byzantium is to prepare sufficiently and make it clear that war will be costly to Byzantium and not a steam roll. In this case, the Byzantium player is incentivized to not war you, because they would just make themselves (and you) irrelevant as other players sim city past you both.

 

[Sostratus]

Horseman doing full damage to cities is brutal in multiplayer

I have to assume the movement of mounted units is what makes this so difficult to deal with. If you found 2 cities close by, for example, the horses could target either. They can essentially “strike without warning.”

 

[Oberinspektor Derrick]

Haven't tried them yet, but once I started thinking about it, it seemed like lots of civs had potentially good counters:

Korea - huge tech advantage. Strong defensive UU.
Eleanor - no way for Biz to hold on to anything.
Ethiopia - I had ridiculous amounts of faith with Grand Masters Chapel. I could just spam units endlessly.
Sweden - those UUs should stop tagmas.
Rome - web of forts backed by ranged units.

And so on. It seems like yes, Biz can steamroll you but most civs should have time to prepare and some advantage to soften the blow. Maybe I just haven't seen how OP they are.

While true that you can always prepare for a Byzantine assault, those civs you listed are not particularly "countering" Byzantium.
Korea needs to be way ahead on tech to actually matter, and early on they might have the science per turn, but difficulty translating that into several eras worth of unit tech advantage. If Korea spawned on the other side of the map and was allowed to get a massive tech lead (as in, tank armies vs Tagmas) sure, Korea is great, but if you spawn near Byzantium? Good luck with that, you are on the clock here.
As for Eleanor,sorry for me being frank here, but that is just a joke.
First of all her ability is rather weak (loyalty pressure wise), and if she even spent so much time filling those theatre districts early on, she is wide open to a direct attack, and her theatre districts and great works are soon Byzantium's.
Finally, noone forces Byzantium to settle cities close to Eleanor, and even if you do suffer from loyalty, slot in a few cards and governors and her loyalty pressure is the least of your worries.
As for Ethiopia (and any faith civ really), faith buying units alone won't save you - heck, it might even feed into Byzantium's interest, as it gives more unit kills to work with for flipping cities to their religion.
If we're going down the route of "just outproduce him with more units", any civ can "counter" Byzantium by going full on unit production.
As for Sweden, if you're relying on a specific unit (arriving at a specific point in the game), you are not really "countering" Byzantium.
Yes the Caroleans are nice, but what if he just straight up rushes you in the Classical or Medieval Era? Or what if he shows up with tanks in the later stages? You either won't have Caroleans, or they will be obsolete at some point.
As for Rome, forts alone won't hold anything. Now I'd say that Rome is good against Byzantium, but that is because of their early rush potential with Legions, which arrives before a Byzantine horseman rush if you beeline it somewhat and use Legions to chop out Legions

Anyway, the quick summary is that this is the wrong approach to Byzantium.
Either you want to kill Byzantium early, fight him away from your borders, or get such a massive later tech advantage that you blunt any attack on you.
This can be done by any civ really (Mali should be very careful though), but you should not rely on certain gimmicks to carry you vs a Byzantine attack (like forts, Eleanor loyalty or hoping that he attacks in the Renaisssance when you happen to have your Caroleans).
If you are on somewhat even tech, and Byzantium is starting to flip your cities (and has Crusade), you are fighting a very uphill battle.
Thus you want to play into other solutions, not gimmicks that at best delay Byzantium.

 

[Siddharth Venkatesh]

I have to assume the movement of mounted units is what makes this so difficult to deal with. If you found 2 cities close by, for example, the horses could target either. They can essentially “strike without warning.”

That's definitely a reason that mounted units are strong in multiplayer. But more than that is just the fact that having double the movement of any other unit in the era is incredibly strong when combat is simultaneous. They are able to attack your units while you cannot attack them, so they get the first strike. They can also last move, first move you, where they move in from out of range at the end of the turn, and then either attack again or retreat before you move the next turn. Mobility is just huge when combat is simultaneous. They also ignore zone of control, which honestly should have been removed if cavalry were to be nerfed, so they are hard to limit in terms of mobility via blocker units. You basically need good defensive terrain and/or a chokepoint to contain them.

The other issue is maybe specific to my experience. All my games tend to be either quick or online speed, and without a mod, Horseman are the only units (aside from Unique Units) with sufficient movement to actually impact ancient (and even classical) era war at that speed. If my city is 10 spaces from the person I'm attacking, it will take 5 turns for a swordsman to reach them (at minimum), and my opponent can produce a lot of defense in 5 turns.

So, Horsemen tend to be the premier ancient era unit, aside from unique units like War Carts and Pitatis. And with full damage to cities, they absolutely melt any contemporary city without walls. You have to block off access, and that can be difficult to do unless you've settled with that in mind. So to defend them properly, you have to build walls, and with Crusade, even that might not be enough. Effectively you end up spending a lot of hammers in things that only help you defend, so it's very costly for you. The horsemen also take down your city much faster than otherwise, so you get less time to build units to defend. It ends up being quite overwhelming.

 

[Tiger Genocide]

Very nice Eagle. I just finished my first Byzantine game as well. However it was one of those games where most things went smoothly. I got the crusade belief. My nearest two neighbors, Rome and Egypt both found a religion, did a terrible job spreading it and fought against each other. I eliminated the Roman religion easily and that was the start of a religious victory steamroll. Declare war on Rome, taking cities and killing units easily. Killing units near Egypt helped me eradicate Cleo's religion and I didn't even slow down the Tagma's before sending them right into Egypt.

Controlling three religious capital cities (standard/immortal) and I just felt unstoppable after that.

My experience on my game was the same, finally finished it yesterday. Wiped the entire map in 181 turns (Online speed), could have been much faster but needed some turns to heal up my horses drag bombards around, etc. Byzantium is absolutely disgusting in their optimum state. I was tempted to try them without Crusade just to see what the difference would be, but then Lily found a bug with them that lets them keep their bonus but with any unit.... I think I will just finish my Gaul games instead. Rolling up a map with them so far is almost the same experience so far.

 

[Victoria]

Crusade only seems to work against the AI. Any half decent player knows the risks and counters. A bit like declaring war on mongols or persia before they can get their bonuses.
As to being a one trick pony, they have another trick, go naval early, it works.