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.
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.
Maybe in terms of the things you can click and knobs you can twiddle, but moving my music into Google Play and off (e.g.) iTunes means that I can very trivially put music on my mobile device (using either that device, or the computer) that is almost instantly accessible offline, and easy to listen to.
That twin gain - ease of sync and offline availability - completely blew Winamp and iTunes so far out of the water that they're in orbit, as far as I'm concerned.
(There are things I miss; multiple genres for a given song/album. Organizing by folder and playlist. Visualizations. Sometimes Google Play will forcibly replace my uploaded files with the wrong version - I still have a few songs that are "censored", and it grates me whenever I hear them.)
I've asked for open-source/self-hosted solutions before, and a few people here responded. One of the solutions looks like it promises to do what I want, though I haven't had a solid chance to look at it: https://news.ycombinator.com/item?id=19555899