For the Byzantines, you need to look at Provinces.
Assuming the Byzantines do well, and conquer places line North Africa and Spain, then besides exploration for explorations sake, there is a genuine opportunity. These provinces, and those like Gaul, or Britannia would all benefit themselves if they could import goods from Asia rather than via Egypt, both providing them the wealth from the trade, and reducing the money that they send to the eastern part of the Empire.
Their explorations could works as in OTL - reasonable open water ships designed for Atlantic use, travel westwards - and find land. (You could tie this into the Vikings)
However, the reaction to the discovery could well be different. No trade route means that the western provinces aren't going to instantly benefit (although a Hispania that continues the attempt and goes south? Yes) but the Roman Empire has an incentive to discern if there is anyone to trade with out West. They spend a fortune in gold on eastern trade, if they can find another trade partner to buy their goods in exchange for gold, then this can address their economic issues. - and who is happy to do that? The Mexica. Roman armaments and equipment for Mexican gold. Set up a series of trade/refueling posts - and the Roman Empire can trade industrial goods for gold, and rapidly increase the rate of urbanisation in western Europe.
The problem is that no matter how you cut it - the Roman Empire needs the Atlantic craft, and then to continue their explorations beyond Hispaniola. Hispaniola remains a fantastic colony - and perhaps the heart of Roman Affairs in the 'Far West', but Mexico has the gold, as does Peru. Finding the Inca and the Mexica for trade partners would be amazing, and would be helped by a great colony "Augustia" in OTL Colombia/Panama. Once that is set up, and trading with the Incans and Mexica for crazy gold - why not spend some of that gold on exploring further west? It worked so well last time