I don't think I've ever been introduced to artists I wouldn't have listened to otherwise through Spotify.

In general I find Spotify's recommendation to be slightly worse than just listening to the radio.

I don't have a good alternative at the moment though. A long time ago I built a music recommendation system based on Discogs that made a vector space based on the genres and then found the most similar albums of one album. When I listened to a track I'd then lookup the album for the track, find the most similar albums and then play some random songs from those albums, but with some controls to make larger jumps possible. It was not using a vector database like FAISS so it was kinda slow and had other issues and with too much bitrot I'd need a complete rewrite to get it working again, but I found lots of new music with it.

Maybe there's some services like that out there now that can hook up to streaming services like Spotify?

On the topic of vector search, I'm fairly certain that Spotify still uses Annoy (https://github.com/spotify/annoy). Like Faiss, it's a great library but not quite a database, which would ideally have features like replication (https://milvus.io/docs/replica.md), caching, and access control, to name a few.