"What is left" of the Byzantine era is an interesting, but complicated question. First of all, what actually *was there* to be left behind? For example, a vast brick Roman city will leave more traces behind then a small wooden fort. But more importantly, archaeologists speak of "formation processes" determining what survives the countless ages. Anything from the chemical make-up of the soil, to earthquakes, war or building projects can alter or destroy archaeological heritage.
A third problem is the amount of interest in Byzantine history. Most of the Turks I've met don't value their Byzantine past nearly as much as they should. Meanwhile, most western people are obsessed by anything Ancient Greece. A lot of money goes to excavating and preserving classical heritage. Byzantine archaeology, not nearly as much. I hope this is going to change in the future, as the public slowly starts to gain more interest in Byzantium.
For Istanbul, I don't really know for sure at all. But judging from stuff like the cisterns, that link of yours and comparable situations in e.g. Rome, I'd say there's a fair chance. Though most of it will not nearly be as spectacular as you'd hope. Bits of pottery, ground traces, etc.
As for the Anatolian cities, I think for example Ephesos shows us what is possible.
http://de.wikipedia.org/wiki/Johanne..._%28Ephesos%29
(The medieval town nucleated around the Hagios Theologos)
For Smyrna, one archaeologist says:
(source: Clive Foss,
American Journal of Archaeology 84.4 (1977) pp. 469-486; Accesable on Jstor for free if you make an account)
Also, a lot of Byzantine heritage actually survives, but just doesn't get as much attention as it should. My professor of Ancient Greek, for example, recently said: "Don't visit Sparta, there's not much to see there", blatantly ignoring it's home to something as phenomenal as Mystras.
http://en.wikipedia.org/wiki/Mystras (I wish I had the money to go here, lol
)
Or for example, Ohrid in Macedonia, has a lot of churches built under the Bulgar Empire but clearly in Byzantine style.
http://en.wikipedia.org/wiki/Church_..._Sophia,_Ohrid and
http://en.wikipedia.org/wiki/Saint_Panteleimon,_Ohrid