pdftops, based on Xpdf, that often produces smaller and nicer postscript) and then
ps2pdfwas a good way to deal with unfriendly PDF files. But, in real, nothing is better than working without intermediates. The following produces a pretty neat PDF file:
gs -sOutputFile=output.pdf -sDEVICE=pdfwrite \ -dCompatibilityLevel=1.4 input.pdf < /dev/null
As side benefits, as this command also embeds postscript fonts, the output looks better in xpdf, and it is decently smaller !