Mark was nice enough to invite me to his home studio when I was a new high school grad to talk working in games as an artist. He told me the story of the fight over dithering. I give him strong partial credit for ending up a game engine/art pipeline coder instead and got to thank him after his most excellent GDC presentation on the lost power of palettized textures https://m.youtube.com/watch?v=aMcJ1Jvtef0
You can see that power in action here
http://www.effectgames.com/demos/canvascycle/ (Hit show options)
http://www.effectgames.com/effect/article-Old_School_Color_C...
BTW: Deluxe Paint has been remade in Python if you want to give it a try https://github.com/mriale/PyDPainter
Wow. The fact that those "animations" (the fire and water effects) were all done with palette shifting is mind-bending.