Adobe doesn’t offer too many options in Photoshop to reduce the size of a PDF. If you use JPEG compression and move the slider to 0 quality, you’ll wind up with an ugly PDF that only saved you 1MB. I was able to cut the size of my test PDF in half (~3MB) by first printing to XPS and then using XPS2PDF. If you’re on Linux, you might be able to do something similar by going to PS and then back to PDF, but it probably won’t work well if there are fonts involved.
Another way to compress your Photoshop PDF is to use a PDF print driver like PDF995. The same PDF which got cut to 3.5MB using the above method was cut down to 1.5MB using PDF995.
You may be able to skip the XPS step by flattening to one layer in Photoshop. PDF print drivers seem to be layer aware when printing from Photoshop, so by flatting you can gain significant size savings and also prevent some display and print issues I’ve seen with thin lines when saving as PDF.
Update 2/3/12: Looks like XPS2PDF is down. I found a trialware which can do the same thing (might fail on images), but you have to do it one page at a time and then recombine the exported PDFs into one file using PDFBinder or something similar. I’ve also had compression success using Neevia’s free online service.