in photoshop, open two copies of the image in the original size.
Magic wand must be set to 'tolerance: 0', uncheck 'antialias', and uncheck 'contiguous'.
1st copy: do background from layer, remove the background colour in the image (the 231,255,255 cyan) then do resize, 50%, bicubic.
2nd copy: do resize, 50%, nearest neighbour.
now copy the bicubic resized one over the nearest neighbour. Select the simutrans special colour with magic wand on the nearest neighbour layer, then select the bicubic layer and delete the excess spill over. Set the Bicubic layer on top of the nearest neighbour layer. Now flatten the image.
This should give sharp edges with no 'halo', yet have a smooth image for the rest.