Lemmings for the PC runs in 16 color mode even on VGA, but it does a cute trick.
It changes the palette in a small gap between the game playfield and the HUD. This means we can have more than 16 colors on screen at once.
Watch it happen live as we step through the rendering in MartyPC.