how long did it actually take to take all the screenshots and make the map?
It used to be ULTRA LONG, so I initially used maps made by Rokker.
Then I discovered useful trick. Irfan View has a screenshoting function which allows you to save image directly into clipboard, removing window's frame. So I can just press screenshot button and instantly paste it into GIMP in correct position, without further modifications (not counting selecting the area I want to paste, to leave only what I want; but that's trivial). This allows to add portions of map in just seconds, and whole Tai Ming took me around 2 hours or less.
reduce file size a little
Now that you mention it, I have a full map of SotN, and with almost the same size, it's just 17 MB. The reason is it has 5 times less unique colors.
So not only I made a smaller version, I reduced number of colors. Medium quality version has 65k colors and LQ has just 256. They are 13MB and 8MB respectively.
(also, the Factory change didn't affect the size almost at all)
EDIT:
So, the LQ version can be easily embedded here. Nice.