The EXIF/XMP data is highly insightful, I didn't even think about how much space those would take up. I updated the original blog post with the information you provided here, and cited you for it. Hope you don't mind.
Metadata would help explain this, since as a percentage of file size, it'd be a lot more detrimental on the first image at 45K than the BMW at 575K.
But sure seems there's something else going on with the first image's circular gradient; PS seems to be dithering its blocks in a moire pattern while GIMP is showing strong banding even on files w/o metadata.
EXIF (APP1) -> 5328 bytes
Photoshop IRB (APP13) -> 5896 bytes
Adobe XMP (APP1) -> 26284 bytes
Adobe (APP14) -> 12 bytes
Total -> 37520 bytes (36.6 kB)
That's 36 kB of metadata, leaving only 8 kB for compressed image data. This explains the banding seen in the English Hard post. The BMW image on the other hand (http://fc01.deviantart.net/fs51/f/2009/313/1/c/Jesus_Mobile_...): Photoshop Ducky (APP12) -> 15 bytes
Adobe (APP14) -> 12 bytes
Total -> 27 bytes
The existence of the "Ducky" section means that the image was "saved for web" in Photoshop.EDIT: Added numbers for the BMW image.
According to jhead[1], GIMP is not including metadata in the saved JPEG.
At quality "13", the file was 46302 bytes. Using the "purejpg" option on jhead, it dropped to 45592, or -710 bytes.
This 45592 bytes is exactly, to the byte, what the original article found.