The only problem with the Byzantines is that they start off rather "big" - quite a large number of provinces and units to worry about, rather a lot of decisions about what to build and where to deploy what. I recall firing them up for my first campaign as the Byzantines but finding it overwhelming, so I quit and restarted as English. Of course, it helps that I am English so the strategic situation was more easily comprehensible.