I've always used Sai for /EVERYTHING/, including maps; however, as Nemena mentioned, Sai does not have a grayscale option, and a height-map must be in greyscale.
I'd suggest saving it as whatever the heck you want, fleeing to GIMP, changing it to 'Greyscale' from there, and that's about it~ x3