Glad I've been able to share some fun with you.
Your document looks all sweet and innocent but inside it is quite the complex beastie. Page 4 has one chunk of 69356 bytes of postscript drawing directives, no images in that mind you, just put text here, draw line there.
Page 5 has one chunk with 120885 bytes! Again, no image data, just pure draw text, draw line, fill box..
In addition page 4 also has a couple images, some Adobe Illustrator CS2 generated EPS metadata, complete with thumbnail images(!), and uses 10 fonts, all of them embedded. Example: GBACLG+MathematicalPi-Four, GBABFF+StoneSans-Semibold and GBACMD+TimesNewRomanPS-BoldItalic.
These are technically known as "complex pages".
I'm personally impressed that poppler managed them in 2 minutes.
Each embedded font requires building the text glyphs by hand from scratch based on drawing directives for each character. Poppler would like to cache all of that hard work away for re-use but the document is so typographically rich with various fonts I'm sure the glyph cache is overwhelmed causing poppler to have to keep drawing and re-drawing the various font glyphs.
The rich collection of super-scripted attributions are kicking poppler in the ribs when it's already on the floor rolling around. The document is using a highly shrunk font to do the super-scripts without adjusting the line height.
Even my Mac struggled mightily to render the document when I opened it and it has 4GB of RAM and two dual core CPU chips.
As far as I can tell the only PDF feature they didn't use were page thumbnails.
With a document this complex the only thing you can do to speed it up on an iLiad class device is to in essence "print" the pages to bitmaps which would drastically reduce the workload for the iLiad since it need only decode the bitmap for each page and throw it up on the screen.