I'm a chat I had yesterday, qstick came up with some good ideas, too.
One involved having all the songs on a giant 3D circular list, so that you get the list of songs coming across the screen diagonally and information on the selected song in one corner, and album / label / song art in the other corner.
Or perhaps something similar to this:
(but song data instead of movie data, obviously)
Also while we're on the topic of song list layout, what are people's thoughts on being forced to use your keyboard (as a keyboard and not a fake fake guitar) for browsing through the song list? There's just so many buttons now, for things like sorting and so forth, that it would be better off just using a keyboard.
What do you think?