I only used a B&W Mac a few times, but I do remember Windows 3.1 doing on-the-fly ordered dithering when running with palettized color (and being very surprised at NOT seeing the dithering on the blue gradient of a setup program once I started using high color modes). Windows 1.0 apparently was capable of doing it as well.