Thanks guys. Sorry about the super-small sample image; I was using the simplest test case possible, a single 16x16 tile, all one color, while trying to figure things out.
I had tried all those RenderingHints in the hope they would make a difference (as well as perhaps ward off issues when creating new images with scales > 1) but they seem to make no difference - the result is still the same, apparent dithering.
I found
this old thread, in which Abuse gives an approach that does work. If you start with one IndexColorModel'd Image, and create a new BufferedImage with a new ColorModel but the same Raster, things are much happier. I'm still not sure why you get differing results when using a "grayscale" IndexColorModel vs. another IndexColorModel, when using a source image that has all pixels the same color, but whatever.