There's a really good technique for getting rid of the wormy or snake-like textures in Floyd-Steinberg: add another term to the threshold proportional to (some monotonic function of) the distance to the nearest preceding dot. This tends to make the dots very nicely spaced. These ideas were, among other places, used in Gutenprint.

A bit of description, and ancient but working GPL'ed code here: http://www.levien.com/artofcode/eventone/

A paper containing the basic output-dependent feedback idea: http://levien.com/output_dependent_feedback.pdf