Agreed. The dog picture actually looks acceptable in jpeg format at 19kB (original 123kB).

Does it? I tried this in GIMP and I get pretty bad block artifacts, discoloration, and blurriness at compression factor 25 (which ends up at ~25kB).

I would say at that point it's arguable which artifacts are preferable (compression or dithering), not compression being a clear winner.

Here's one done with jpegoptim -m 40, which gets it down to 28k:

Original 123k picture on top, 28k picture on bottom:

https://imgur.com/a/hZy46K3

Yes, this looks pretty much like my version.

Maybe I'm just nit-picky, but I do quite clearly see greenish squares, especially on the forehead and nose area.

Probably not enough to catch my eye, but strong enough that looking at the picture for 5 seconds I would say "boy this was compressed way too much".

You've gotten rid of 78% of the bytes. That's an extremely little price to pay in quality for that kind of gain

Yes it is less than perfect. It looks a lot better than the dithered examples though.

Tell GIMP not to include the EXIF and XMP data (which doesn't get any smaller when you decrease the quality). Then tell it to use 4:2:0 chroma subsampling, and set the quality to 24 or so.

It just looks a bit blocky/fuzzy when I try this. It doesn't look great, but it retains much more detail than the dithered version. It looks a bit better at the same size as a HEIC image.