I use amaroK
for handling playlists. It can also rip files into ogg, or mp3 although to be honest I tend to use KaudioCreator for that.
amaroK uses either SQLite, MySQL or PostgreSQL as a backend, and can easily cope with a huge amount of songs. It just may take a little time to run over your collection first.
Has some handy features like pulling album covers from amazon, can get the lyrics of songs, and even has the ability to get info on the band thats playing through Wikipedia. Also it can set up lists and send them to K3b to burn a CD.
Massilvly configurable, and can use whichever backend Audio gives yoy the best results for playback, I use it with Gstreamer since it tends to sound better on my system.