oldboy,
Byzantines: Constantinople is IMO the best location on the map - Victory location, controls Bosphorus, amazing bonuses around (incl. wheat, quarry, silk). A Royal Port will turn it from a huge pop/trading center into a production power-house as well. However it is surrounded by many great powers and where you settle your colonies is a very tough decision.
On the European side Serbs and Bulgars are both very close to you, and should not be neglected. Historically they delt terrible blows to the empire. Your goal should be to move along the coast towards Greece securing the absolutely key location around Thessalonica (horses + timber) and then rushing to get the iron in Macedonia, which is eaqually important. If you win this race you will get Hellas and Pelopponese where your cities will be limited to 6 pop indeed, but will get you gold, tar, wine and olive oil - nothing less. Further down the road, conquest of rich Crete should also be your objective. This of course means you leave both northern most red points on your mini-map to Bulgars/Serbs.
Settling in Asia is also key and eventually the biggest threat should come from there - either the Turks themselves, or more likely as I found out Fatimids/Abbasids pushing towards Europe. You have 2 locations to target: one south in the Bursa-Bergama area, and another on the Anatolian northern coast in the area of Amastris. You can develop there 2 big, rich cities that will be the sentinels of Constantinople in Asia and the future basis for conquests there.
I would build Thessalonica + Larissa first, then Bergama + Amastris if there is still time, and then turn to Greece proper with 2/3 more colonies before sailing to Crete and other Aegan islands if there is still time. That will give you 7/9 cities around the best one in the world potentially, and a good shot at victory from there on if you play it well. An issue though is that Constantinople is very well placed to build key early GWonders, which will go against your expansion plans.
Good luck!