Dear Pandora executives:
I hear that your business model's in jeopardy because of increased licensing fees for streaming Internet audio. I suggest that you diversify your income stream by licensing your database for media players, enabling them to dynamically construct playlists using the player's local collection.
Most modern music devices have the capability to construct dynamic playlists based on ID3 tags (for the less technical in the crowd, ID3 tags are how your iPod knows the artist, album, etc. of a music file that you download). The problem is that although ID3 tags include features such as release year and "genre", these don't suffice to construct a cohesive sounding playlist. Pandora's dynamic playlist construction based on musical qualities handily beats construction via arbitrary categories like genre.
Conversely, although people increasingly own rich media Internet devices with unlimited data plans (like the iPhone and the G1), WWAN Internet connectivity is still not pervasive enough to provide a seamless streaming radio experience.
Meanwhile, the cost of storage (both hard drives and flash memory) is falling so dramatically that people can save both encyclopedic music collections and a fairly substantial database of metadata about those collections on local storage. (Any worries about "giving away the store" by letting people cache slices of your database locally should be alleviated by the realization that people will require periodic updates, as the music industry — despite their insistence that digital piracy is strangling them to death — continues to produce an avalanche of new music every week.)
There is a window of opportunity here. By providing a mechanism for good dynamic playlist construction, you could get a licensing fee on every player sold. And since you'd be providing metadata about songs, instead of the songs themselves, you would pay no streaming fees.
Alternatively, you could at least write software that opportunistically plays a song from the local device when available, instead of streaming, thereby reducing streaming fees and improving audio quality on such devices. (When someone listens to a station long enough, chances are that the user will already own a nontrivial fraction of the songs that come up.) Notice that if you write this app, then it is a tiny, incremental step to simply disable the streaming engine and play songs from the local device only. This would be less dramatic than caching the Pandora database itself locally, but it would reduce network bandwidth to an RPC to the Pandora server on song switches (and again, you'd avoid the streaming fee).
Once you have Pandora cached locally, you should take a page from Wikipedia and Delicious and allow people to collaboratively tag music with your attributes. (There's a potential spam problem here, but there are defenses which I think would be fairly effective.)
It seems likely that you've thought of these ideas. Maybe you've even found good reasons not to implement them. But just in case you haven't, I thought I'd suggest them.