Saving Visio diagram as PDF

File-> Save As -> Change File Type to PDF (the actual description in Visio 2010 is "Save As Type...").

To get the size down to what you want, assuming you are using Visio 2010 - go to the Design ribbon at the top, and change "Size" to "Fit to Drawing"

Credits: DavidChenware @ superuser.com