Probably don't even need to go that far - I suspect a 75% JPEG would balance filesize/quality acceptably.
I wonder if doing a 8-bit PNG with only 64 colours might even give a good balance - just tried it on the above image and it comes out at 103KB (i.e. 40% filesize of the JPG).
There are PNG optimising utilities that can probably do that in a scripted way.
EDITED: 25 Jan 2011 12:02 by BOUGHTONP