I played the ItR both with Austria and Byzantium, but I enjoyed Byzantium much more.
(it was on king level, but now I play on emperor)
I founded Constantinople and then Adrianople, I think it was in Thracia. I grew a little and kind of ignored CSs except Ragusa and Belgrade. After a while (I had 4 cities), I started a war against the Ottomans (which took Jerusalem) and destroyed them (got a bunch of points for both being allies with Jerusalem and conquering islamic cities). After that, I wen t with the same troops against Saladin, and conquered them as well. By that point, even Russia hated me (at the beginning of the game, she was my personal trading partner), and I decided to ICS and conquer Austria. I spreaded my religion to the ex-Ottoman and ex-Ayyubid cities and my faith started to grow. I, then, settled a really large amount of cities, like 20.
I had a lot of space: Cherson was in the middle of the Aegean sea, Varna was in Greece, Ohrid was in south Turkey, Ani in north-Black Sea (I feared a Mongolian DOW), Samosata in south Greece and Theodosiopolis in western Egypt. I went from the Austrian borderline to the whole middle east and part of north Africa. With such a large populace, I had some happiness problems... but eventually that went by (in the end I could adopt the Order opener - as I finished the tech tree - and happiness was really plentiful). I then saw that yummy Klagenfurt laying close to Cherson and decided to dow Austria - too bad it was at the Hussar age =/
I managed to conquer the whole Austrian territory (except for Salzburg, which Augsburg got before me, and Innsburg, wich Warsaw destroyed), so my empire was even bigger and I had a lot of points. I, then, saw some neerlandeese settles aproaching thracia. William went aaaall the way through Europe to found Maastricht, Nijmegen and The Hague really really close to my european territory (which spamed around the west coast of black sea, going like, 8 tiles into europe) and next to the ex-austrian territory. I had a lot of gold, so I rush bought an army and destroyed his cities back there, well, more for me. After that, I converted every single city of mine to Eastern Orthodox and managed to conquer Groningen from William (with my Austrian-war-veterans). By that point the game ended.
I won like, 80% of the HREs, most of them because my religion was spreading fast and because of a technique some of you guys might call an exploit. I dowed Spain and the Celts, but didn't battle them. I had the largest military in the game, so, after 20 turns, they offered a fat peace treaty for me. Other non-battled war was against the almohads because they got Gibraltar and I needed to pass my caravels. Being able to buy monastaries in every city gave me a huge faith boost against other civs, so I was able to win all the "generate the most faith" CSs requests. France, unfortunately, got all cultural ones.
I also used my extra spy to lay in city stated before the HRE, as England was really rich and disputing CSs with me, so, getting twice more coups than them was nice. I used my dromons for coastal support against the Ottoman coastal cities and the Ayyubids ships, but against Austria, I only used them to help me conquer a stupid city she decided to found in Italy. The Cataphracts were mostly nice against the Islamic civs, as against Austria/Netherlands, I already got Knights. Bullying some city states (even my long time ally Belgrade, which I had 253 influence with) also gave me some money.