A Byzantine colonial empire would hinge, in the end, on the solid control of Egypt. The Levant itself wouldn't be necessary, but it would be a logical extension and provide a land connection with Egypt. If those two regions are secured, they can expand outwards into the Indian and Pacific oceans.
Settler colonies are indeed unlikely at first. You might see a late-term colony in Oceania, but most of the colonies are going to be for money. A repeat of the Portuguese/Dutch conquests is most likely. The best target for colonization would most likely be the Spice Islands, in all regards. A large amount of income could be sent back into the empire to fortify its lands and help it in border wars against whomever is its opponents at the time. Be it an expansionist opponent in the Balkans or Caucuses (Russia/Hapsburgs/Tatars/whomever pops up) or vengeful Turks, Arabs, or Persians from the east and south, there will be some conflict to sap money from the coffers. The Byzantines will assuredly go after money-making colonies rather than founding a new homeland.
To that end, the targets for conquests would be relatively logical. Getting control of the Horn of Africa to provide a base for which they could guard against pirates and keep the Red Sea open, the Maldives, Ceylon, and various parts of the Cape of India to keep the trade lanes open. They would probably puppetize the larger powers in Indonesia, and conquer the sparsely inhabited sections.
If it is desired to go down to Africa, Zanzibar would be the first target (especially if Oman has it. Must deny them it) and the only other major conquest I could see would be Madagascar. Tripoli would be the target in North Africa, but anything farther than that (or to the west at all) would probably require Sicily.
Perhaps not a Byzantine Raj, but would it be more likely that they only conquer part of India, especially the southern tip or the Bay of Bengal?
In the end, for them to be a colonial power, they will have to have a large continental empire. They simply have too many strong enemies on too many borders. They are not so fortunate as some of the western European colonizers. And that does discount any other land grabs they might try to make in Europe. I think it comes out to the same path. A timeline would have too many butterflies to predict in a few paragraphs.