
The blocky fog is the spans fog (which is relatively fast *nudge nudge nudge nudge*) while the sharp accurate fog is zbuffer-reading fog (which is horribly slow and is similar to your fog). In more subtle fogged maps you won't even notice the blocky imprecision of spans fog. I have also dithered the fog, but not with noise. You can easily tell this is DrawSpans16 i've put fog on given the 16 pixel step of the depth
and fyi this zbuffer reading fog is a reworked version of the elusive unused ApplyFog function from FTEQW's abandoned software renderer to use with my fogmap that I use with spans fog. I tried to make to it with dither. Considering Laser Arena's performance I believe they also have slow Z-reading fog, plus their sky is fogged.
Plus with spans fog, if you don't want to fog the sky, then simply don't edit the sky spans!

Another thing that can be tried is dithering the model's shading. It can be done effectively, though that has no relevance on supporting new features for mappers
my point is since you have an engine with a mission for more without heavy performance compromise (weird colored lighting method withstanding) I suggested spans fog like here as an alternative. It might work out for the heavily unrolled c loops you have going more than it does for me