En Linux

Utilizaremos ghostscript, una herramienta para manipular archivos con contenido PS y PDF.

Instalamos en Debian/Ubuntu:

sudo apt-get install ghostscript

O si tenemos Archlinux:

yaourt -S ghostscript

Ejecutamos el siguiente comando:

gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -dPDFSETTINGS=/screen -dNOPAUSE -dQUIET -dBATCH -sOutputFile=PDFREDUCIDO.pdf PDFORIGINAL.pdf

PDFORIGINAL.pdf: La ruta o el archivo del PDF que queremos poner a dieta.
PDFREDUCIDO.pdf: Será el nombre con el que se guardará el PDF.

En Windows, Mac y cualquier navegador

Podrás elegir la cantidad de compresión, y si quieres: la versión compatible, el formato de imagen y la posibilidad de quitar comentarios o elementos superficiales. Muy recomendable.

Link: http://convert.neevia.com/pdfcompress/