On Android you can use NewPipe for a similar experience. For obvious reasons it's not on Google's Play Store, but you can get it from F-Droid or Github.
The Tubular fork of NewPipe is worth noting, https://github.com/polymorphicshade/Tubular n a Revanced patched YT app would also work.
You essentially described Musi, although it still serves you the Google ads and its own occasional ad every now and again
[1] https://apps.apple.com/us/app/musi-simple-music-streaming/id...
Whether this was legal is... a gray area, it was a somewhat legitimate company that won some kind of Canadian startup contest on TV, but the music industry was, very predictably, furious at their business model.
Eventually, Apple got scared enough of being sued along with them that they caved in and removed the app, but that took far longer than I thought it would.
There's a good article at https://torrentfreak.com/apple-removes-parasitic-streaming-a...