@mrbarrett just pointed me at pianobar, a command-line client for pandora. It gets rid of the need for flash player, and allows you to bypass some of the limitations of the web client (you can skip more than 5 songs!).
To install (on Ubuntu):
sudo apt-get install git-core libao-dev libfaad-dev libmad0-dev git clone git://github.com/PromyLOPh/pianobar.git cd pianobar make sudo make install
enjoy!
Jonathan Cran 
If for some reason you like GUI’s for your media playing experience, try Pithos. It uses the same backend as pianobar (libpiano).
http://www.webupd8.org/2010/02/pithos-is-lightweight-pandoracom-client.html