This requires some thought as to exactly what is going on here and what you are trying to do.
You are probably aware that there are essentially 2 types of PDF document, those where the text is ready rendered and those where it is not in which case what you actually have is a fancy image of the page.
So if it is of ready-rendered type (its an images essentially), you could get some mileage by converting to real images, reducing the definition of those images and converting back to pdf. the convert program will do this.
You should also (in 12.04 or greater) put pdf into synaptic. You'll get a slew of utilities including the following, some may be useful for what you need. Perhaps pdfedit, pdftk, poppler-utils, pdfmod, qpdf,
What if your pdf is of the other font-based variety? Of itself I am not sure there is much you can do here. After all, information is or should be stored efficiently in such a situation, so its not clear what you could do without loosing any of it.