I have a very large music library. Digging though directories to find music is many shades of impossible. I was using Songbrid which indexed my collection and allowed me to search it. However songbird is nearly unusably slow for large collections and they have dropped Linux support.
If you’re running only on a local machine, I recommend
Amarok hands down. It has one of the best interfaces for handling large collections, and doesn’t bog down under the size of my collection (20K+ songs)
If you’re running over a network,
kPlaylist is a great web interface to music collections, though I use
mt-daapd to manage and make my large collection (20K+ songs) available over the network. The DAAP server automatically shows up in iTunes (my music player of choice, given such a large collection), and can be made to show up in Songbird or Winamp via plugins. DAAP will stream the music over the network so you don’t have to manage sharing the files yourself.
gmusicbrowser is the only application that could read my (600 GB) music collection without problems.