You must use fonts whose licenses allow embedding. Not all fonts do, and I know of no program which will embed fonts which are not appropriately licensed. Acrobat 9 Pro will warn you when saving if embedding is turned on and fonts exist in the document which cannot be embedded.
AFAIK, all of the 'Windows standard' fonts (the ones that come with Windows--Arial, TNR, Tahoma, etc.) are embeddable. The analogous Mac fonts may be, as well. Commercial font foundry fonts will likely not be. Freeware fonts found online may or may not be, either by design or simply because the creator didn't bother to include the necessary licensing information.
You do have an option. It will not leave the text editable, but from your OP the issue is the printer wanting to ensure fidelity to the original, not text editability. If you have Illustrator you can convert the text to outlines. In Photoshop, use rasterize text. Save a copy of the file with editable text first, in case you need to do further editing, as this will render the text uneditable. However, it will print exactly the same for the printer as it does for you, and he won't need to have the fonts available. |