Is Illustrator really the most suited tool to draw a (fairly simple) map from scratch and print it on a flyer? Are there any other tools or apps out there that might make this task easier?
There are actually online tools that can do this. However, personally, I would start out with a google map screenshot and work from that - in Illustrator.
You could take a round on the net and search for brushes and plugins for Illustrator that have ready-made map-elements. Here is but one example of what you can find: symbols ready made. Such as:
These post might also be helpful to you:
QGIS (http://qgis.org/en/site/) has a PDF export function, but it isn't exactly easy by any stretch of the imagination, as it's a full GIS program, but can export to PDF. You can pull in OpenStreetMaps data as well. Open-source, free.
Here's a good tutorial: http://multimedia.journalism.berkeley.edu/tutorials/qgis-basics-journalists/
OpenStreetMaps (and Mapbox, which uses OpenStreetMaps data) both allow significant theming and export options, including PDF export, of maps. This would be the best filetype to open and manipulate further in Illustrator.
Inkscape is another open source program you could use. But as others have suggested I would personally stick with Illustrator. Instead of grabbing a screenshot of a map you could start with a vector file instead.
Take a look at this website I created. http://openvectormaps.com