I've just downloaded some PDF documents and when I opened them I was surprised by their horrible quality. The fonts aren't anti-aliased in any way, it looks like some cheap nearest neighbor algorithm. I can't remember a thing done to Adobe Reader 9, so what's going on and how do I probably cure this?
There is no general answer to that.
If any document gets rendered that way, you should check your preferences. There are sttings for smoothing text and lines, and you can select the screen type.
If it is only a specific document, it is possible that it is either an image (find out by zooming in, and you should start to see pixels), or that it has its text turned to outlines, and your smoothing settings are suboptimal (see above). Zooming in should give you hints here too. In such a situation, you can't do much besides contacting the issuer of the document and complain there.