IMO there are several different periods in which the Ottoman Empire could be stillborn, and depending on when and how, the ripple effects could be very different.
First scenario: IVth Crusade does not happen, or is a failure.
Byzantium eventually gets a competent ruler or two within the next decade or so, and manages to hang on to everyone's surprise. The Mongols show up on schedule, and eliminate the Seljuk sultanate, creating a power vacuum in Anatolia; the Byzantines buy the Mongols off, and once they are gone, quietly pick up the pieces. The remaining independent Turkish principalities in Anatolia survive on the Byzantine sufferance, as buffer states, or as local powers, protected mainly by the fact that Byzantium does not have the resources or the manpower to truly retake Anatolia.
IMO this kind of scenario would result in Byzantine, or, rather, extremely Hellenized Balkans... the main powers would be Serbia, Bulgaria (if the POD is after Bulgarian independence), and Byzantium, with the latter being the most influential in terms of social structure, religion, etc. Hungary could be thrown into the mix as well with its own territorial designs, especially on the Dalmatian coast, although given that the Mongols are still coming West, Hungarian designs could be severely hampered, giving the Byzantines a chance to pick up some of the pieces while no one is looking.
In Western Europe, it is likely that any sort of long-range military expeditions ("crusades" that would have been directed against the Turks in OTL) would be sent in Spain and North Africa, resulting in faster reconquista, and possibly a greater mess in North Africa - however, since the Great Schism of 1054 would be constantly reinforced with no real attempts by either side to come to reconciliation (as there is no direct threat to Byzantium, it does not feel threatened enough to really care), there will be stronger Orthodoxy, and potentially stronger secular authorities in XIIIth-XVth century Europe. In this manner, chances are the Protestantism is either incorporated into one of the main doctrines (thus either an Orthodox or Catholic church would end up with many of eventual ideas thereof), or would not even rise at all.
Second scenario: No Othman
Presuming that in the chaos of XIVth century Anatolia, House of Othman fails to rise to prominence, and no other Ghazi state manages to do that either. By then, the moribund Byzantium has somewhat bleak prospects, however, better than in OTL, as it does not face major threat from the East, only having to deal with Serbian, Bulgarian, and Latin (Western European) threats. Chances are, Byzantium would be able to hang on to most of OTL Greece, along with the coast of Smyrna, while the principal conflict in the Balkans would be between Orthodox and Catholic branches of Christians. There might be several empires of relatively similar strength competing, these being the Serbs, the Bulgarians, and the Byzantines - possibly with the former two laying some kind of a claim to Byzantine throne from time to time. It would be hard to tell who would realistically come out on top, depending on circumstances it could be either of the three, or even all three coexisting in some shape or form.
Western Europe would generally try to meddle here and there, trying to keep whoever is on top weak, but it is also likely to concentrate more on internal problems - thus a Hundred Year War, if it still happens, could end up being a larger conflict, involving many other nations; the Middle Ages might end up lasting just a bit longer, since there would be much less of an idea of European unity (which, as ephemeral as it was, was generally used when Europeans had to combat an outside threat - the idea was that better a rival Catholic than a Muslim, especially the Muslim who had the desire and the means to crush the armies of European rivals and to expand his territory), and less means for outward expansion. At some point something akin to another IVth Crusade might arise, simply in case Byzantium cannot adequately protect the trade routes, or is being beaten down too badly.
On the other hand, the Middle Ages might end up being shorter if Byzantium/Balkan powers hold on, and block a potential trade route to the Far East. Then, the age of exploration could start earlier, with more resources put into it.
Third scenario: Ottoman Empire is stillborn
There are several potential PODs here, one being the previously mentioned one that in late XIVth century, the Ottomans lose the battles they won in OTL against the Serbs and the Bulgars, and as such are confined to Anatolia, where they end up devolving into series of internecine conflicts that leave them easy prey for just about every European adventurer wanting to set up his own private kingdom.
Another POD is that the civil war between Bayezid's sons after his defeat by Tamerlane has a different outcome, and results in permanent splintering of the Ottoman domain, with resulting kingdoms exerting nowhere near the power and influence of the united Ottomans. Considering by then the Ottoman presence in Europe was IMO somewhat hard to reverse, we might end up with a moderately sized (predominantly Muslim) Ottoman successor statelet in Greece and Bulgaria, which would compete against similar statelets in Smyrna and the interior of Anatolia.
This would give Byzantium just the chance it needed to play these Ottoman remnants against each other, and possibly pick up the pieces here and there - however by then, there is next to no chance Byzantium could ever regain its former prominence as anything other than a regional power at the very best. Within a generation or two, the European Ottoman successor states are likely to be reduced by everyone who attempts to carve them up, just as the Asian Ottoman successors would fall prey to endless attacks by the Latins, Byzantines, other successor states, other Turkish statelets, and just about everyone else.
IMO this might result in greater (Western) European presence in Anatolia, simply because there is a large amount of what essentially would be no-man's land, free-for-all where the population pressures are still fairly low. Thus, instead of directing their energies into the New World exploration, most European countries would simply end up sizing up chunks of Anatolia as much as they can do so - although OTOH it might give even more of an impetus to Portugal and Spain to colonize.
But: I can imagine that reborn Byzantium could have some interests on northern shores of Black Sea... maybe. But if Khanate of Crimea is wilting on the wine without Ottoman support and slave-market, then territory north of it, what's basically our Eastern Ukraine -- it's for grabs, IMHO, since I cannot imagine why Byzantium would want it and how it would hold it. And that... could be a beautiful beginning.