I have a kindle, but when I tried to read this pdf of von Neumann's “The Computer and the Brain", I found that some letters were completely missing.

On average a couple of letters per page were absent. It looked fine in other pdf viewers, so I knew the data was there. Following some suggestions online, I found that by far the best solution was ghostscript:

gs -o repaired.pdf -sDEVICE=pdfwrite -dPDFSETTINGS=/prepress computerbrain.pdf

As for the other suggestions, Calibre and pdftocairo fixed nothing. And while mutool did work, I ended up with much larger borders which the kindle wasn't able to trim. That means the text is much smaller than necessary.

By the way, it's well worth reading.

Dear reader, good news

Missing letters and dodgy rendering is only ever a problem with scanned documents - computer-generated pdfs render without any problems. Here's an example chosen entirely at random:

⁂