The best ”algorithm” for discovering new music was digging through profiles on last.fm back when the social functions of the site were still active. Sure, it was a lot of manual work, but the results were amazing. It wasn't completely blind, I found that people I had high similarity with, it was more likely I'll like what they like, even across different genres. Sometimes people were nice and took the effort to recommend based on my profile. I got introduced to varied music, different genres and even a bit from different countries.
The worst was Pandora, which did recommendations based on breakdown of musical instruments and elements in the song. It did what it aimed to do pretty well, only it was a bad idea. It gave you a lot of uninspiring music that sounded like a bland copy of something you actually liked.
Spotify's recommendations are not super awful, but definitely feel closer to Pandora's style. I wonder why is the result like that even though I'm sure they train their model based on listening history.