Thanks for the tip!
After reading your post, I did a quick search and found that Ubuntu comes with a small command-line tool called pdfcrop, also available at
http://www.ctan.org/tex-archive/support/pdfcrop/
It does a per-page crop of all the white-space, in the margins. I tried it on one of my PDF books (Open Source ESBs in Action), and though it did take a long time (15 minutes or so), the result was really good. It looks a bit weird in a normal PDF viewer (the title page was stripped to just the title text), but on the PRS-600 it looks great.
So, thanks for the inspiration... this will make reading papers and books so much more convenient.
By the way, I also found this tool:
http://pdfcrop.sourceforge.net/
Haven't tested that one yet though.