If you'd rather start from scratch, you're talking about cartography with the difficult fact-finding and accuracy stuff cut out. It's not half as daunting a task as it initially looks - the key is in the preparation.
Broadly speaking, a typical cartography workflow (minus the research and geolocation) is:
- Decide what details ('traits') you are including. This will become the 'palette' you have to work with. For example:
- Roads (and how many types of road, lane, alley, etc?)
- Rivers, streams (and how many types? Varying or constant widths?)
- Other natural features (woods? Types of grassland? Or even, if it's small scale, individual trees?)
- Buildings (and when will you pick out individual buildings, and when do you show blocks? And how many types of block - are there types, e.g. residential, you want to distinguish?)
- Any non-physical regions (toponyms) - for example, districts?
- Any other landmarks (e.g. markers for events, facilities...)?
- Any topography (e.g. contour lines to show hills, dips, etc)?
- Work out what level of labelling you want. Go through your list above, and pick out the ones which you want to be things that can have labels. You won't label everything of that type, but you need to fix before you start which types of labels can exist.
- Are there any specific things you want to give iconographic or pictographic images for? These could be, marking unique or important things, or illustrations and embellishments like the fantasy monsters on medieval maps. Another list.
- You've now got the outline of the palette of your map. Turn it into something you can work with. In illustrator, the most straightforward way is to create a graphic style or brush for each trait, and a paragraph style or character style for each type of label, and a symbol (these can be simple placeholders for now) for each pictogram or icon.
- Then, start drawing your map, using paths, polygons and text using the above palette and nothing else. As for where to start with a fictional map, I'd recommend starting from the ground up. How do you imagine the scenery? If you're showing any topography, rivers, etc, start there.
- For a fictional map, build the town in a logical way: start with key main streets, main buildings, districts, features, then think how the town or city might have evolved. If this building is here, what will tend to be near it? What will the main routes to and from be? Build it up until it feels like a plausible town and has the right level of detail and completeness.
Everything in a map signifies a type (and usually also, subtype) of thing, and everything about a town or city has a reason for being where it is. Maps look daunting to create, but when you pare it down to a palette appropriate for the detail you want to focus on, and when you progressively build up the town from a logical starting point, it's not that daunting.