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.