I used to try to make heightmaps in Paint because I thought it would be easier, but I find that Easygen makes unnatural looking terrain with those bitmaps.
I find using Photoshop’s brush tool is a lot easier and makes it look more natural. Also, try using the “Blur” effect, it makes terrain blend in better and again make it look somewhat more natural.
BTW, I’ve made heightmaps in a various amount of dimensions, I don’t think it matters at all. Larger sized heightmaps = larger sized map area. 
