I have now learned the reason. When you upload a medium or large book to Apple, iPhoto creates a PDF file with images that are only 150dpi. The small books are at 300dpi, which is much more suitable for printing. Consider the fact that at 130dpi, iPhoto warns you that the image will not look good printed, and you can see the problem.
The solution? Edit ~/Library -> Preferences -> com.apple.iPhoto.plist and change both BookTargetImageDPI and BookTargetMediumImageDPI to 300.000000. This will dramatically increase the size of the file sent to Apple, but should make the results look a lot better.
[robg adds: I haven't tested this one, but it's evident in the plist file that the DPI setting for the medium and large books is 150DPI, versus 300DPI for the small books. I'm not sure why Apple would have it set this way, nor if changing it will really improve the printd quality -- isn't it also dependent on the resolution of the source images? Anyone with a better understanding of DPI and printing, please leave a comment!
If you want to edit the plist file and you're in 10.4, you'll either have to use Apple's Property List Editor (part of the Developer Tools) or convert the binary plist to XML first via the Terminal (plutil -convert xml1 filename), and remember to convert it back to binary (binary1) when you're done -- and remember to quit iPhoto prior to editing the plist file! I think I'll wait on the edit until reading some of the comments...]
Update: iPhoto6 resolved this issue; no need to use this hint if you've upgraded.

