The Arabs will flip all of Mesopotamia (minus Sur/Tyre if its a 3000BC game) and Egypt. The Turks will flip any cities in Anatolia that aren't in your core. In addition, the Seljuks will get large conqueror stacks in Anatolia and near Babylon/Baghdad, and the Mongols will get a small number of conquerors on two of your cities when you first meet them.
Assuming your city count remains at 5 or higher, your core will never shrink or move. If your city count ever falls to 4 or fewer, your core will be reduced to just Constantinople. This will not reverse, even if your city count returns to 5+.
EDIT: made an error with the info for Turkey's spawn; see two posts down for correction.
So what happens if Byzantium spawns with less than 4 cities? is their core forever Constantinople?