Microsoft is an applicable precedent here - when it was found that they had breached competition law in using bundling with Windows as a way to gain unfair market dominance for Internet Explorer, the remedy was to require that Microsoft offer users a means to select and download competing browsers on first use. The Commission can then fine them a significant amount if they fail to comply with the decision.

Of the options you've suggested, the second seems most likely.

One potential solution that may also work is instead of not taking the 30% fee, to allow Spotify and others to take payment through another channel (e.g. by bouncing users to a web-based payment gateway) - the enforcement there just becomes an injunction to not enforce the app review rules that prevent affected apps from using third-party payment providers in addition to or as an alternative to payment through the App Store.

The difficulty will be where they draw the line. A lot of third party services compete with built-in apps/OS features: for instance, Dropbox/iCloud Storage, Notes/Evernote, Office 365/Google Docs/iWork. The difference between Apple Music and Spotify (and presumably also Tidal and Deezer etc.) is really clear, but quite where you divide up these markets is a real tough issue in EU competition law. An Apple Music user could very easily be a Spotify user and vice versa, but not every iCloud user would necessarily be a Dropbox user.