I'm a GNOME user, but on my brother's suggestion I tried Amarok a month or so ago, and never looked back. I've used most of the popular music players for linux as well as iTunes & WMP, and I'd actually call Amarok the best on any platform. It's not even close.
One really nice feature is the database integration. I think every application should have this option, and not just because I work for a database company. Amarok can keep all its information in a MySQL database, and that includes the song lyrics it pulls down from the web.