What about a combination of a stronger al-Andalus state, one which manages to hang on and hold at least southern Iberia (I rather suspect it would actually have to hold the whole peninsula though), and that regime getting strongly on the outs with the Ottomans? Perhaps for reasons of religious divergence, perhaps out of simple political conflict?
So it remains an Islamic-run nation and the Europeans give up on the idea of dislodging it, but being opposed to the Ottomans, it seeks diplomatic relations with the western Christian realms. And in this situation, Iberians are still the pioneers of Atlantic exploration and trade.
The upshot might be Western Christendom, in its own schismatic divisions, getting used to the idea of relating to this Muslim state as yet another player in the game of European politics, and the Iberians coming to think of themselves as part of that world too.
What this does for North Africa is, gives the local Islamic powers there choices--to submit to Ottoman hegemony, or to align instead with Iberia.
A distinct Western Med Islamic subsociety might result, one that is in closer communication with the Christian powers to the north as a result of ties mediated by their Iberian ally.
Meanwhile overseas the Iberians who trade with the Indian Ocean and beyond by going around Africa would have the advantage, relative to OTL Portuguese, of being Muslims and therefore less unwelcome in East Africa and less unfamiliar in India and the East Indies. Whereas once the Western Hemisphere lands are discovered, the Iberians might well seek territory and converts to Islam there, but the rest of the Europeans would not feel in the least bound to back off (not that the OTL Treaty of Tordesillas was much respected by other Europeans, certainly not by Protestant England and Netherlands but not by Catholic France either) and in fact might find the religious factor an additional spur to land-grabs in whatever the western continents would be named.
I'd guess it would be Iberians who find them first, probably the northeast tip of OTL Brazil, while attempting to follow the trade routes around Africa. But also that the news would leak and meanwhile English expeditions like that of Cabot would happen eventually due to the news of Breton fishing grounds and the old lore of Vinland plus the geography-inspired notion of a Great Circle northwest passage to China all conspiring to suggest an expedition in the old Viking direction might well pay off one way or another. Especially if there is murky word of Iberian discoveries to the southwest.
So then there'd be a rush to the west, and this might draw Iberia's North African allies in closer, with Iberia having such a strong hold on the mouth of the Mediterranean.
I can even vaguely see a possible Italian connection, with some major trading city-states like Venice probably kowtowing to Constantinople and their rivals, frozen out of eastern Med trade, seeking ties with Iberia and her Muslim north African associates. Perhaps, to give extra demographic oomph to land grabs in the west, the Muslims would go so far as to assign territories for the Italians (therefore Catholicism) to colonize, if these Italian colonies will assist their Muslim neighbors and allies against Northern European encroachments. The Catholic establishment in Rome thus sees the spectacle of two opposed sets of Unholy Alliances with Islamic powers, some Italian states aligning with the Ottomans, others with Iberia, and perforce both wings of the Muslim world are entangled with European politics and the whole thing--Catholic or schismatic-from-Catholic Western Christendom, Islamic Africa, Islamic Asia--all being drawn into one big political continuum, with far-flung theatres of exploration, trade, and settlement with a side of conflict in the Western Hemisphere and the far East.