Primero instala, si no lo tienes instalado, el programa Ghostscript con el siguiente comando:
sudo aptitude install ghostscript
Una vez instalado Ghostscript, ejecuta el siguiente comando para reducir el tamaño del PDF:
gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -dPDFSETTINGS=/ebook -dNOPAUSE -dQUIET -dBATCH -sOutputFile=pdf_reducido.pdf pdf_original.pdf
A continuación podeis ver las opciones de -dPDFSettings:
dPDFSETTINGS=/screen (72 dpi, menor tamaño y peor calidad)
dPDFSETTINGS=/ebook (150 dpi, calidad media)
dPDFSETTINGS=/printer (300 dpi, alta calidad)
dPDFSETTINGS=/prepress (300 dpi, alta calidad preservando el color)
dPDFSETTINGS=/default (casi idéntico a screen, pero con calidad ligeramente superior)