> I'm pretty sure Apple stayed with Google's Search, because otherwise Android phones would've had (at least) a branding advantage
Apple stay with Google's Search for two reasons:
1. It's the best search product. 2. Google give them bucket-loads of cash
This isn't rocket surgery.
In the alternative universe where Google didn't do Android, Apple would be able to extract more cash from Google for its search placement, at the very least, since Google would have fewer alternatives.
With Android they can exert control over the mobile platforms. Google Search, GMaps, GMail are the default on all Android devices and beyond.
Now think of Apple. At some point they wanted to switch to Bing, but they didn't. Don't really know the details about why they didn't, but it's quite easy to make a guess ...
I'm pretty sure Apple stayed with Google's Search, because otherwise Android phones would've had (at least) a branding advantage (Google is a synonym for search), not to mention that Google Search is still more potent than Bing. Without GSearch, they probably would have lost GMaps too. Then the argument for Android would have been: ooh, but it comes with GSearch, GMaps and GMail. Apple is not stupid, they couldn't put iOS at a disadvantage, in a world where every other phone comes with Google built-in.
So you see, Android is the platform that keeps them relevant in a mobile world that's tightly controlled by carriers and walled app stores.