Yeah, if your entire product's strategy relies on someone elses platform and you don't have multiple income streams, or ways to acquire customers, you'll be exposed to these sorts of things.

I wonder how big Spotify's android base is. I know they get my $10 a month.

That's very different. You can exist without a good SERP, you can buy ads, acquire users elsewhere, but you can't exists outside the Appstore on the scale Spotify plays.