A handy thing to make random terrain BMPs is the "render clouds" filter in PhotoShop.
Painting elevations by hand is a very tricky thing, as most brushes are too hard-edged to give anything but cliffs. Also it's very hard to see the difference between a couple of close values in a greyscale, but just a difference of 2-3% can make an elevation difference of several hundred feet... itwill really stand out. That's why most hand-painted maps (like Pizza) have such extreme cliffs in them.