par481, you may also have missed a button that changes the pregenerated map types from small to medium to large/huge. When starting a new game and selecting a map, under the list of available scenarios there's a button named something like "Change Map Type". Click that and you get some larger scenarios.
Alternatively, use the map designer as suggested above.
