Here's a trick. Before you do anything.... Add noise. Then use error diffusion. Looks pretty good for how crazy fast it is.

Figuring out the strength of the noise is tricky. Usually 5 to 10 percent. I'd suggest random RGB and not monochrome noise(so not quite how you've coded the randomness, but similar idea), as this should create more unique values and reduce patterned artifacts.