Regarding the age of exploration, ship building technology and navigation techniques will advance in the next millennium Islam or no Islam.
How the Byzantines fair in alt 15th-16th century world is really dependant on what that world is actually like, how strong the Byzantines are, what the geopolitical situation in the Mediterranean is, etc...
I could see the Byzantines trying for an Indian Ocean policy-getting into the money spigot that is India and its surrounding locations.
I wonder, considering that the Byzantines would probably be more tightly bound economically with the Med, whether we'd see a Med-Northern Europe Divide, rather than a Europe-Middle East Divide, and as a result it isn't the Spanish/Italians interested in going west - but instead the Northern Europeans, effectively revisiting Norse Saga rather than hunting for China.