Have you tried any of the following free tools from here at MR?
PDFLRF
Rasterfarian
PDFread
SoPDF
PaperCrop
The first three are all PDF > LRF converters (or allow that at least), and yield good looking results in most cases, though I think they're all image based, so can result in very large file sizes.
SoPDF and PaperCrop are PDF > PDF "converters" that can be used to make a PDF look better on a small screen by, e.g., stripping the margins and/or dividing multi-column PDFs into separate pages. SoPDF isn't image based unless the source is, so I tend to use it if I want to preserve a smaller file size.
If start with a very badly formatted PDF, at present, there's not much that can be done, however, as far as I know. The algorithm in
this thread might be worth experimenting with, but it looks rather drastic, and I haven't found the time to try to make it work myself.