It seems some of these services (e.g. Spotify) don't really do musical similarity, but instead emphasize indirect "other fans also like" similarity.

That tends to disregard many reasons you like a particular track, and does especially badly when the liked-track isn't part of a uniform style for an album or artist.

I recognize it's a heck of a lot easier to implement, but it's still a disappointment.