I managed to "downgrade" to Acrobat 7.0 and, with a couple of tweaks, do a new "proper" PDF for this issue. It's still bigger than it should be (590K, but that's better than 622K--I think it should be around 400K), but the first page now seems to show up after five or ten seconds, not 20 or 30 seconds.
So I've replaced the ugly-but-fast PDF with a pretty-but-not-so-fast version. Some time over the next month, and with some useful info from Seth Finkelstein, I'll try to figure out the problem so as to solve it for future issues. For now...well, I'm neither Irish nor a beer-drinker, so I guess usual weekend stuff will have to suffice.
Update: A minor tweak to the document template (cutting the banner out of the running page header and adding it as the first element in the document itself, if you care) seems to have solved the problem: The PDF is now down to the size it should be, and the first page seems to load in a second or two.