This is a comparison of an image I drew for a book that I've been working on (forever ... really ... forever). The four shade grayscale was created in PSP using their "X colors" command after first putting the image in grayscale.
I tend to leave anything with that small of a palette in gif format. I'm not certain that having it be a jpg (which is more lossy) adds much to the equasion, but I could certainly look into that.