I am not herewith contradicting Dimitris Almyrantis’ answer. For Dimitris Almyrantis is awesome and stuff. I think I’m saying the same as him.
I don’t think much would have been different, except that there’d be Greek names instead of English and Spanish; the naming principles, I suspect, would have been the same.
Byzantine town-naming procedure was usually to name places for emperors and the like; there are a lot of Justinianopoles and Irenopoles and Leontocomes and Theodosias. Cf. Mary-land, James-town, Philip-innes, Georg-ia.
A lot of places were left with their indigenous names, just as the New World was in our timeline. Mexico would likely have remained Mexico, although it would have likelier been transliterated as Metzikon or Mesikon [meʃiko].
In Modern Greece, there is an inordinate number of St X and St Y towns, often as jerryrigged replacements for local Slavonic or Aromanian or Arvanite placenames. The Spanish didn’t stint on such town names; I don’t know that the Byzantines ever did that, but it’s possible that would have happened in the New World. No San Francisco, for example: he’s not an Orthodox saint. But as Russian America (Alaska) shows, you’d get places like New Archangel[sk] = Sitka, St Paul, St Dionysius = Fort Stikine.
There are also a profusion of New X and New Y places, founded by refugees. I think New Smyrna would have been perfectly feasible in the Americas, for instance. (After all, there’s not only a New Smyrna in our timeline in Athens; there’s a New Smyrna Beach, Florida—an ill thought out colony of Greek settlers.)
I don’t have OP’s command of detail (https://www.quora.com/If-the-Byz… ). From Theme (Byzantine district), I am guessing Notiōn (“of the south”) or Notiakōn for Australia, by analogy with Anatolic Theme.