Export to PDF/X-1a and you'll avoid this issue most likely. Fonts are included with this format. Your PC counterpart most likely does not have the fonts in your file, hence the jagged fonts when he/she views your file.
Kinkos has its own file process and you have to send them files online. They are very particular about format as well. Go here for more:
http://www.fedex.com/us/officeprint/onlineprint/