Strangely the on that had the best discovery for me was Google Music. It just seemed to eerily read my mind and I stumbled on so many good titles that I love. Rarely did I need to skip any song during, say, a workout playlist.
As for the UI, I loved the Google Music one... when I was on Android. Now that I'm on iOS it's totally alien and just unusable because zero iOS conventions are respected, like I'm in a virtual machine, it's just frustrating. I find all of the other music platform UIs quite awkward and despite its flaws Apple Music is still the best for me.
Seems like we hit a wall and "all MUAs suck" just changed the M from "Mail" to "Music".