The symptoms here are that the Computer Modern Fonts look bad at most resolutions, though they print fine. The fonts in the DVI or PS files look fine when generated with latex and dvips, but ps2pdf or dvipdf both produce the same poor output that pdfLatex does.
I have only noticed this problem on my Debian Testing (Sarge) install.
As root, you need to run the command
updmap. Then as your normal user, you need to run latex and dvips once. You might notice that dvips generates more output than it used to. Your fonts should look fine now.
Thanks go to Byron Clark for helping me figure this out.