Yet another audio player with built-in database for easy browsing of local music files. It has no playlist, instead it simply plays songs from current search results. These queries can be saved to give you something like "dynamic playlists". It also has support for queing up songs to be played.
If you keep your music files organised, or if you want to listen to songs just downloaded to a temporary folder, you can use the filesystem view (powered by the KIO library from KDE). BoomBox can also keep track of internet radio stations for you.
Audio players are a matter of taste, maybe this one suits you?