» Acrobat6.0以降（確認してませんが7.0もおそらく）なら、
「PDFの最適化」が可能になってます。
画像の再圧縮及び適応型再圧縮、フォントの埋め込み有無、
互換性変更などが可能です。

ただ、画像が容量肥大化の原因でない場合もありますので、
その場合は再圧縮をかけても、容量軽減できるかどうかは
未知数でしょう。
特に容量指定されてる場合は、その容量に収めることが
可能かどうかは別ですから。

» フォントがアウトラインで、埋め込みでない場合、ファイルサイズが大きくなってしまいますが？

» アドバイスありがとうございます。
ご意見を踏まえまして身近なところでも相談した結果、
ＰＤＦ上で編集するしかないかも、ということになりました。
もう少し勉強してみます。

» 単純にAcrobatからPSファイル（Windowsなら*.prnファイル）に出力したものを直接Distillerにかけても同じですか？
その際にDistillerのジョブオプションの設定を変えても同じですか？
画質以外の内容を変えずにサイズを小さくするにはDistillerのジョブオプションの設定を変える以外に方法がないように思いますが…。

ジョブオプション変えても変わらないようなら、「匿名」さんの言う通りテキストがアウトラインになっているか、パスで複雑な図形が描かれている可能性がありそうですね。AI9以降の透明の分割とかで。

作者にどんな設定でPDFを作成したのか聞くのが一番早いと思いますが、何をするにしてもまずは原因を特定または絞り込んでおいた方がいいんじゃないでしょうか。