Try blocking the map out with the huge terrain brush - grass where you want land, then forest where its impassible, dirt2 where its going to be arid, and cliffs to denote future mountains. After you figure out what the gameplay requirements are, you can carve out huge paths in the forests or add forests to block off areas.
I like to figure out the entire gameplay for the scenario and get to a first playtest run before even thinking about actual map design. A blank map is good since you can make huge alterations without ruining anything...of course, its mostly up to personal preference and how you like to do it.
"Excellent could be any map that has the quality of a ES random map or ES scenario. AoK is an excellent, award winning game. That's where I'd start." -AnastasiaKafka
"Hard work is evil. Bitmaps are stupid. Working on a scenario for more than one afternoon is stupid. Triggers are stupid. Testing your own scenario is stupid. The world is stupid. You are the Greatest." -Ingo Van Thiel