Grayscale for the terrain, and green for the Lemmings!
Incidentally, at least on the Amiga version of ONML, the lemmings in the mini-map are yellow, not green. (The terrain is green btw.)
So as you can see, even the game designers themselves know that there is absolutely nothing special (read: not worth imitating) about certain aspects of the mini-map.
The grayscale idea could work, although interestingly, the more I think about it the more I might prefer the "monochrome" one. The monochrome mini-map in the original game does have the advantage that you don't notice the stretching as much, since the lack of colors and low resolution means you basically can't make out the terrain very well. It is kinda weird to call this an "advantage", but it does make the stretching much less noticeable.