The problem with dithering is that it is added noise (read: entropy) that needs to be preserved in the image file, which can make the compressed image file bigg

The problem with dithering is that it is added noise (read: entropy) that needs to be preserved in the image file, which can make the compressed image file bigger. You can actually achieve quite good results by just cranking down the quality on a jpeg. You'd have to go really low quality before it looked as bad as these dithered images. Also, jpeg supports greyscale, although you might find that keeping the colour in there really doesn't add much to the file size at all anyway, especially if you set an appropriate chroma subsampling ratio.