To scale the page size of a PDF down, I'm using Adobe Acrobat Pro 2017. Inside the Acrobat Pro DC 2015 preflight profiles there is a profile for PDF corrections that can be adapted to ones needs. I was searching some time ago for a different (free) solution, but couldn't find something else that worked for me for publishing.
However, you can also scale to a non professional PDF with Preview.
Just select Print (Cmd + p) -> choose another paper size (or first create the size that you like) -> select to scale to paper size -> then use the PDF dropdown menu to Save as PDF. In Preview, in general, most of ones PDF editing needs to be printed out to another file and confusingly not to be saved by the Save command.
Reducing a PDF size further is something that really depends on the individual PDF and what you consider as "without sacrificing quality". IMO, the best results for a smallest possible file size is by writing directly to a small PDF file. Maybe Keynote is not perfect to do so, because it's an app for presentation and not primarily a publishing app. If you could upload a typical single PDF page, it would be much easier to give advice.
You could try to create an individual filter in ColorSync-Utility and apply that, but this didn't work well for me in the past. Again, personally I'm using Acrobat Pro for reducing file size ,if I don't have the source file, but there are plenty of other tools available (some of them free from time to time) that can convert images inside a PDF to a lower resolution and deleting unnecessary chunks of data. Depending on your PDF, those tools could fail, too.
http://appshopper.com/search?search=PDF+Compress+Expert
Sometimes placing a PDF in some DTP app like InDesign, QuarkXpress or Scribus and writing another PDF from it is a better solution, sometimes even that fails. That's why I recommend to use a publishing app from the beginning for the most minimal PDF file size.