Not in particular order:
1. Emperor Alexios in The Alexiad scenario, since he starts in a relatively poor situation surrounded by enemies and having lost Anatolia to Seljuks. He was also an awesome Emperor and I recommend reading the book carrying the name of the scenario.
2. Doux of Epirus, the Palaiologoi. As the final dynasty of the Empire, they are an interesting choice.
3. Romanos IV Diogenes in 1067-1071. He was the man who lost Manzikert so you might as well change history.
4. Start just after the end of the Latin Empire (~1262). The Empire can now hardly be called an "empire". Surrounded by Latins and Muslims, it's a challenge just to survive.