When Blurry was researching graphics conversion I recall finding an algorithm developed by one of the original Mac developers that doesn't use randomized dithering. It looks great on old digitized Mac pics from the day. It's documented in one place on the web - the author actually got the algorithm from the original programmer but hasn't published it, which is a shame.
Are you thinking of Bill Atkinson's algorithm, documented here http://verlagmartinkoch.at/software/dither/index.html ?
If so, it's also an error diffusion dither, with a different kernel. I tried it, actually, and looked slightly worse. (I have a variant of my app that lets you pick from a handful of algorithms.) I'm using a modified Floyd-Steinberg algorithm. Modified in that, so far as I can tell, the sample code I based it on is buggy in a really bizarre way... but it looks better than the corrected version! I'm still scratching my head over that one.
Anyway, suggested app name: vn2c, of course. ;-)
Ooooh, that's a good one. I'll make a note.