Indeed the embedded fonts are responsible for the file size.
If you replace the font with a built in one, the file size for a simple invoice goes down to about 4kb.
To do that, it becomes a bit messy. You need to rewrite the classes extending from Mage_Sales_Model_Order_Pdf_Abstract
and Mage_Sales_Model_Order_Pdf_Items_Abstract
Then, replace all calls to
$font = Zend_Pdf_Font::fontWithPath(Mage::getBaseDir() . '/lib/LinLibertineFont/LinLibertine_Re-4.4.1.ttf');
with
$font = Zend_Pdf_Font::fontWithName(Zend_Pdf_Font::FONT_HELVETICA);
The built-in fonts you can choose from are:
Zend_Pdf_Font::FONT_COURIER
Zend_Pdf_Font::FONT_COURIER_BOLD
Zend_Pdf_Font::FONT_COURIER_OBLIQUE
Zend_Pdf_Font::FONT_COURIER_ITALIC
Zend_Pdf_Font::FONT_COURIER_BOLD_OBLIQUE
Zend_Pdf_Font::FONT_COURIER_BOLD_ITALIC
Zend_Pdf_Font::FONT_HELVETICA
Zend_Pdf_Font::FONT_HELVETICA_BOLD
Zend_Pdf_Font::FONT_HELVETICA_OBLIQUE
Zend_Pdf_Font::FONT_HELVETICA_ITALIC
Zend_Pdf_Font::FONT_HELVETICA_BOLD_OBLIQUE
Zend_Pdf_Font::FONT_HELVETICA_BOLD_ITALIC
Zend_Pdf_Font::FONT_SYMBOL
Zend_Pdf_Font::FONT_TIMES_ROMAN (or Zend_Pdf_Font::FONT_TIMES)
Zend_Pdf_Font::FONT_ZAPFDINGBATS
There are plenty of extensions that do that for you, for example https://github.com/firegento/firegento-pdf (also on Magento Connect) uses the built in FONT_HELVETICA
.
The Firegento_Pdf extension makes customizing with the PDF's more pleasent in more then that regard by the way (plus, the default PDF's look nicer already).