I really recommend doing a first map at a smaller size to get things where you'd like them. Then take a copy of that map and scale it up to your final size. Use that as a background image in your paint program and draw the detailed information on layers above that (at least one layer per type of terrain). Having the rough cartoon in the background helps a lot in keeping things consistent, I find. Working with the smaller scale and simpler map also allows you to iterate quickly to forms that you really like.