I liked your strategies, nice to see different ones from my own. I have been evolving it since my first play with Byzantium, my aim always the biggest empire in Europe, so now I'll explain exactly what my strategy is (the previous one was just some tips):
Starting:
Building
Best thing to do is: Workers. Constantinople, Thessalonika, Antioch and Alexandria have a worker, so none of them should make one. The rest should make one worker. With this mass worker starting it'll make you the top techer of the game until France gets Chivalry (which in my strategy you should avoid entirely). After the workers are done, improve your tiles: Get the resources, Farm where possible (your best improvement for all the game), Mine the hills and Cottage everything else (Grassland Cottages are the best).
Constantinople, Thessalonika and Alexandria must make a Work Boat. There is fish in all cities, so you must grab them (Alexandria will increase borders before the boat is done). Antioch I normally make a Spearman to help against the Sassanids (if poor Antioch can make it fast enough).
Unit Tactics
There is 1 swordsman in Athens, Thessalonika and Hadrianopolis. They are enough to handle the Slavs. Constantinople has 2 Spearmen and 1 Swordsman, and Nicaea has 1 swordsman. Send Nicae's Swordsman and one spearman from Constantinople to Caesarea, the other Swordsman and Spearman from Constantinople send to Sinope. The swordsman from Antioch should defend Aleppo and the one from Jerusalem can be placed firstly on Antioch (to replace the one from Aleppo, in the case he dies), then after making more troops (as I guess Sassanids can spawn up to near Tarsus and Iconium, even if you didn't lose any city) you can see where it fits better. From now on you're well defended from both threats. Sassanids strike is swift, Slavs take longer to disappear.
Teching and Evolving
Go for Stirrups. No manorialism. Manorialism will be good after you can make lots of Horse Archers, as with lots of Horse Archers no improvements will be destroyed and no workers will be taken, so you'll tech like a god. Then get Manorialism (Cottages!). Then you should tech to get the possibility of changing your civics to the medieval basis: Feudal Monarchy, Feudal Law, Manorialism, State Religion (already from beggining) and Militarism (the only good expansion civic in my warmongering strategy).
Now you should survive and develop greatly. If you aim on getting UHV1, after the Workboat focus on Culture. Hippodrome and the Belfry are great, later you can make Marco Polo's Embassy or the Round Church (or both) and maybe the Shrine of Uppsala. This UHV is easy, as Constantinople is free to only build culture related buildings. I would focus Wonder production in Constantinople first, so you can make a Golden Age soon (the best use of GPs in RFCE). If you lack a culture building at any time, make Horse Archers. They are your best friends (3-movers on the Byzantine Empire is the only thing you need until your UU).
The Arab Revolt:
Building
Your workers are working the tiles to make your country strong, so you have to protect them: Spam Horse Archers all along the places that can make them quickly (20- turns), including Greece. 3-movers reach your Greece-Anatolian extremes in 4 or 5 turns. Sinope should make a Work Boat and the places that can't make Horse Archers in 20- turns, you should build a Manor House (for the needed stability against the Arabs). Constantinople is now focusing on Culture buildings (my strategy always aims at the UHVs, if you don't: Horse Archers!). Alexandria should get both its water resources, so 2 workboats before making troops.
Unit Tactics
This part is easy. All Anatolia should send the HAs near Syria province border (you can use them against Sassanids first, so you can scatter them through this eastern anatolian region). Press SHIFT while hovering the mouse in Syria to see the Arab flip zone. You should have at least 10+ HAs in any of those roaded tiles just above the flip zone, under Aleppo, east of Antioch, so they can reach Damascus site in 1 turn (Actually I put them one tile east of Antioch or in Aleppo itself, depends on the plague, as from there they can't attack you in 1 turn, but you can) . They only need to be there the turn before the Arab spawn, so you must remember this (you can check their spawn date on the Civilopedia). If you lose any Greek swordsman, use some surplus HAs produced in Greece to compensate (you can make a lot more HAs in this time then it's needed). Send your archers from Jerusalem and Tyre to Alexandria, and any HAs built there too for countermeasures if this strategy fails (and to get Tripolis later). You have to leave Tyre and Jerusalem empty so no troops flip.
Teching and Evolving
Keep doing what you were doing: Improvements and tech to liberate the civics you'll need. You should at least change to Militarism ASAP, to get less instability penalty for capturing cities. Manor Houses and Courthouses on your strong developed country will be built quickly and will let you live without being dismembered. Changing civics in the beggining is a great strategy for all civs in RFCE, as you wont lose anything for bad stability when you've just been born. Then focus on getting Cataphracts your awesome UU.
To crush the arabs is easy, wait for the spawn, then keep waiting for the flip. In my experience the Arab spawn never gets Tyre before the flipping, and with your overwhelming forces near Antioch I doubt they'll even move that way. Deny the flip. Damascus will have 1-2 Archers. Attack it, capture it, delete your remaining units in the flip zone. Done! You destroyed the arabs, all their huge stack that appeared near Jerusalem and the other from the spawn disappears, as you got their only city. You need lots of HAs exactly to make the arabs go for Tyre instead of Antioch or Aleppo. The plague obviously struck you before that, but it surely wasn't enough to break you.
For the bulgarians I've never developed a good countermeasure against them because they always seem to be randomized by the game. They have few Konniks in the beggining (5-), so just counter them. No flip from Bulgaria. The best thing I can imagine is let it live, make some cities and in the appropriate time strike and get them. They love to wage war against you, but they are eager to become a vassal too. Do as it pleases you (conquer or vassalize), but not in the spawn, wait for a better and more stable moment (you'll probably be struggling to avoid being with negative stability after the conquest of Damascus and the need to conquer Tripolis - but don't worry too much with this negative stability by now, worry with the arab respawn as they ALWAYS flip damascus in the respawn), and of course now that you have no strong enemies and a huge stack of HAs, focus on developing your cities and more importantly your Stability.