It's not clear to me from the article what remedy they're proposing. Seems like it could be any of: * Drop the 30% fee * Drop the 30% fee for apps the compete directly with Apple apps. * Allow users to install other app stores.
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.