[MacGizmo]

There's really no reason to outline the fonts in InDesign, and I suspect that may be your problem. Just embed them when you create the PDF. Also, if the font has an effect such as a drop shadow or other transparency effect applied to it, you may want to check the "flattener" settings to make sure they're set to high-resolution.

It's difficult to troubleshoot without actually seeing the PDF file, as you suspect, it might just be your client's installation of Acrobat. Perhaps it is as simple as they have the view set to something other than 100% which will cause "jaggy" fonts and vector lines.