could always do what i've done now lastfm isn't free, run ampache on your home server, and use that to stream a massive collection, no recommendations though
I can't test this out since I don't have my unit yet, but the last.fm website mentions an API available to developers. A little investigation shows that mainstream Banshee allegedly has last.fm integration. Banshee has also been ported to the Pandora, but I have no idea if all the features are implemented. You could try that, unless someone already has.
I was going to suggest trying out OpenPandora on the Open Pandora, but it only has a windows release.
Edit: Although the discussion page for the port mentions options are disabled and the program is a little unstable.