So, I finally broke down and bought an iPod the other day. After spending a minute working with the click-wheel interface, I remembered the Event Horizon UI I read about when I was at an ISP (http://research.sun.com/techrep/1999/abstract-74.html). It seems to me that this UI would be great at navigation with a click-wheel. I am listening to a song, then while the song is playing, I can focus on the tree that this song is a part of, and navigate the leaves of the tree. This may be based off of genre, artist(s), or a collected preference. Also, this tree could lead me to other artists on iTunes music store, if I happen to be online. The click-wheel seems pretty obvious, to me, to lead to a tree-based implementation of the Event Horizon UI. A tree-based implementation would allow me to arbitrarily pick the sink of a horizon. This node may be the sink I am interested at this moment, but I might choose a deeper or higher node as the sink of interest, allowing me to see the leaves I'm interested in at any point.
To explain this more, perhaps I am listening to Christina Aguilera, then zoom out to see the tree of Solo Female artists, then zoom back in to see Pop Music Solo Female artists. Then I then click over to see Alternative Solo Female artists, then decide to listen to Fiona Apple or Aimee Mann. But the point is the tree, or perhaps undirected graph in this example, is navigable based on zooming. (as an aside, playlist organization as an undirected graph might be worth looking into)
The basics are you hold the results at arms length, then bring it closer to see the details.

Of course, people much smarter then me probably have had these ideas already...