https://www.foobar2000.org/images/img/main-black.png (ignore the white-on-black, that's orthogonal style change).
See that Filter box? That's a search that, within the scope of your music library, works better than Google's or Spotify's. It's an incremental search box (I believe web kids call that "Instant" nowadays?), that filters the album list by your search about as fast as you type.
I don't think it's built for "a different kind of user" - Spotify UI is pretty complex, because everything from search to managing playlists presents you with a pretty noisy UI that makes you click around a lot to find what you want and not click on what you don't want (Foobar never "suggests" you music it fully knows is not what you're searching for). Being a user of both - having switched to Spotify when it became easier than bringing an external drive full of MP3s to work - I can tell the basic UI interactions are of similar complexity, except Spotify is a bit more confusing at times.
Foobar's incremental search is such a useful feature I ditched Winamp for it back in the old days, and I still use it as a go-to example in product/UI development sessions.
I'm sure there is a way to search, but I think Foobar is maybe built for a different kind of user than Spotify, etc.