Wow, I've never looked that closely at the PDF export, but yeah, the rendering of curves is terrible. Example attached for the curious--the text is 75mil high on the PCB about 87mil in the PDF. Are you using an outjob for this? If so, there's a "TT Fonts" checkbox in PCB Printout Properties under Printout Options, does this make any difference?
Otherwise, perhaps you could try sending the case manufacturer a DXF or DWG? I think truetype fonts are exported properly in those formats. Or, worst case, if you've already got access to CorelDraw or somesuch, replace the text there, using the text from Altium's PDF as a guide, and save as a new PDF?