When you generate blue noise by shaping in the frequency domain and transforming, the samples are gaussian distributed, not uniform, as the author mentions. I wonder if you can transform to a uniform distribution by sorting the samples, choosing 256 bins of equal size, then quantizing each pixel into those bins. That would be fast: O(n log n) in number or pixels.

Changing from gaussian to uniform is a distortion that presumably adds harmonics, but since they can only be higher frequencies than the original, the noise should still be blue.