I have looked at the files using PSE, but not on the Nexus yet. Preliminary comments:
1. I do not know why the 256-color indexed pngs are 60%-65% of the size of the 256-shade grayscale pngs. That seems like something isn't equal, and I want to know the explanation. I prefer to use a grayscale format for grayscale images.
2. Neither of the images have true black (and they both should have) nor enough true white. Before going down to 256 values, the image needs to be stretched so that there is black and white. Just use your eye to estimate how much. In PSE, if you select part of the histogram, it will tell you how much in % pixels you have selected. Like this:
"I think the image needs 5% black and is about 65% white." (this perhaps is the first image with more white in it)
Select area on histgram showing where that many pixels on each end fall.
Use levels to stretch the values to match what you saw on the histogram.
Most scans don't use the full scale from 0-max, so most images need this stretching. It should be part of your process, while at full color depth. It makes images pop properly (i.e. they look dull without this operation).
3. There's little for it so far between the different formats. By far the most visible artifact (to me) is the aliasing in diagonal lines, and those are obvious in all the images. Please go back to the original and see if they are present there. I have found no specific tool to smooth them, but something needs to be done. A standard smoothing or blur filter can certainly improve it to some degree.
On the bright nighttime thing, I would see if I could add partial transparency and what that looked like. That might be nice when people pick textured or tinted backgrounds in general (or not
).