They do get a strong start but they're also almost certainly going to be crusaded against, ally-less in Europe, and either fall behind or take a 50-year break to westernize and catch back up. Still a strong contender, and one I meant to do this with at first, but got caught up in the egyptian missions and turned towards india.
As Castile, though, I can call the crusade against them. It may work out. I managed to catch them while they were engaged in another war, so I could take another Algerian province as well as a dead-Byzantine core I can release and crusade in the "1st Castillian Holy War of Give-Stuff-Back"
Well, obviously, it's doable with a lot of countries if it's doable with Byzantium. Still, I don't think you should underestimate the staggering amount of tax base to be found in Persia and India to make a play for the Med, precisely because you won't get the overseas penalty. I'm actually playing another Byzantium game now, where I went east instead of towards the Mediterranean, and if I hadn't permanently lost control of the HRE due to a bug, or if the cores hadn't expired, there's no good reason I couldn't have cleaned house in Europe, too.
Without the extra 50 years to consolidate you need as Byzantium, the sky's the limit, because between Europe, North Africa, Aden/Arabia, Persia and India you can really maximize that AE burn-off. You'll need to fight your way down to Persia and then sail down to India to use those at the same time, but it's absurd what you can do as the Ottomans with a little elbow grease and an Overseas Expansion CB. Rush to secure the Indian coast and rack up a coalition if necessary, but after that you've got so many different areas to fight in that you don't really need to worry about them. Geography is everything. :V