EYG - Read the Byzantine thread from the MTW Guides section:
https://forums.totalwar.org/vb/showthread.php?t=31248 Lots of good ideas there.

Like you I started mt first Early Campaign as the Byzantines at the weekend and I have the Egyptian Sultan cornered in Antioch. Managed to get a fort built in Naples after quashing a couple of uprisings. Also, touch and go in Sicily. I move my Byz Infantry there every other turn but the Sicilians keep retreating to their Keep and not fighting. Then back to Naples to quell the next uprising with a several starred General now. I do not think I have ever wanted to get Peasants built so badly to get some loyalty in that Province lol!

Tomcat