@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