k2pdfopt. It slices up pdfs so that you can read them without zooming on a much narrower screen, and since its output pdfs are essentially images, it eats everything up to (and including )very math-heavy papers, regardless of the number of columns they have. Also, it works with scanned stuff too.

(And even though the output is a bit bigger than the originals, I didn't encounter any problems with 600 page books... the result was about 50 megs tops.)