I'm looking for something similar to iTunes for my Linux box. I've used xmms, [g]mplayer, and xine extensively. ([g]mplayer is my movie player of choice). However, I am looking for something that works like iTunes. Not in the sense of working with the iPod, but the ability to have a library and sort based on Genre, Artist, or Album is critical. A search function like the iTunes search would also be nice. Oh yeah, it also needs to include support for m4a/AAC, as most of my music is AAC. (Yes, I know I won't be able to use songs with iTunes DRM)

Try this one out
This media player come with gnome, It is my favourite music player. Its User interface is similar to itunes.
But in FC$, rhythmbox don't support any kind of media except ogg (I don't know how to fix it). But I think you can configure it in Gentoo