You can actually combine error diffusion with your probability-based approach, which helps reduce patterns if I remember correctly (it's been a very long time).