As for search, the full-library keyword search is more than enough 99% of the time I'm looking to jump to an artist/album, but if you want to get more complex, smart playlists let you search your library for files using just about any criteria and combination you can imagine (no regex though, not that I've ever found need to regex search my music). Smart playlists are seriously iTunes' most powerful feature and I've never seen it satisfactorily duplicated in any other music player.
iTunes' database/spreadsheetness is it's most powerful feature - you're not limited to just one set folder hierarchy for navigating your music. iTunes gives the user a myriad ways to look at their data; sometimes too many, really. TBH, all the newer UI views that make iTunes "pretty" instead of looking like a spreadsheet are simply more silly and time-consuming to navigate. Fortunately they've left the spreadsheet-style views available for people who aren't afraid of data.
iTunes certainly has lots of issues, especially on Windows where it's buggy and (from what I hear) slow, and it suffers terribly from a decade of feature-creep and try-to-be-everything-for-interfacing-with-iOS, but if you simply use it as a music library/player it can be fantastic.