I stumbled across this site called Pandora, which was created by the Music Genome Project. Essentially you type in the name of an artist that you like listening to, and they play songs by that artist and other artists that sound similar. The first 10 hours of the service are free and then it’s $36 per month after that. Pandora works through your browser, so there’s no reason that you couldn’t use it everywhere you have a high-speed connection and, although I don’t have a PDA with wifi, it seems like it should work with any wifi-enabled PDA that has some sort of browser.
If you find an artist that you like, you simply click the icon of the artist and it gives you the option to buy the track from iTunes or the CD from Amazon. Furthermore, when you click on an artist, you can create a new station from the artist or vote on whether or not you like the artist, which I believe will help customize further stations that you create.
It would be damn cool if you could use this service with XM or Sirius; that would definitely make me invest in one of those 2 services.