The cleanest way to exchange documents between Windows and the Mac OS is (as you suggest) to have users agree on a common set of fonts.
If it isn't possible to get the users to come to an agreement on Fonts Types, Styles and sizes, and the system substitution isn't acceptable, then it will be necessary for you to purchase a third party solution for document distribution. Most of these packages will also maintain the integrity of graphics as well as fonts. The following is a list of four popular packages for this purpose:
Company | Package |
WordPerfect | Envoy |
Adobe | Acrobat |
No Hands | Common Ground |
Farallon Computing | Replica |
You would be best advised to call these companies and explain your requirements to make sure that this is the type of solution that they are looking for, or if you need more information on the products.