The Quartz filters that Preview uses to shrink images/PDFs sucks. But you can fix it!
Basically, just copy and edit /System/Library/Filters/Reduce File Size.qfilter, changing the compression and maxImageSize parameters. Here's the article I followed:
http://www.macworld.com/article/1168311/shrink_preview_files_without_ruining_image_quality.html
