I am not a historian, but I have some experience with visualization from numerical physics. So basically there are three ways to generate graphics:

1. Drawing: It does not really matter if you are drawing with crayons or photoshop, the upside is that you are essentially only limited by your imagination. The downside is, that it is hard to get anything correct. ( And at least in physics, it is not really a accepted technique.)

2. Specialized tools: Something like Vizit or Graphviz, I am not really sure what similar tools in history would be. Depending on the tool, the upside is, that you get good results quite quickly. But if you are trying to do something advanced you will hit a wall at some point, because the programmers did not anticipate your need.

3. Plotting scripts: Take a scripting language like Python and a visualization toolkit like MatPlotLib and write a program that outputs your graphic. The downside is, that nothing is ever really easy except if you can reuse a script. But you have the full control over your graphics as well as a defined method how the graphic was generated.

My experience is, that plotting scripts are the way to generate graphics. They have some disadvantages compared to specialized tools, if the tool is designed to do what you want. And they have at first a rather steep learning curve. But they have the nice advantage that you can do basically anything you want. So the advantages become more pronounced the more experience you have with them and the more specialized your application gets, while at the same time the downsides matter less and less. So I would suggest you use something like basemap for your maps.

The serious map people are all GIS people. That means learning how to use ESRI's ArcGIS. It is one of those terrible programs that takes forever to learn, is entirely unintuitive, is "powerful" unless you want to do something it isn't in the mood to let you do, but has a monopoly on the whole damned market so everybody puts up with it. I've played with it and never gotten very far; even doing supposedly simple things like exporting existing data to other formats, or changing projections of maps, is an exercise in painful, tedious frustration.

You aren't going to make things as pretty as the SHP without some serious training with GIS. There are, however, more and more opportunities for people to learn how to use this kind of mapping technology, as mapping is one of the more attractive and explanatory "digital humanities" fields these days. The Google products, in particular Google Earth, can help simplify some of this work as well. Google Earth can let you point-and-click to add layers and polygons and lines and markers and labels everything good like that. It doesn't look too pretty, but once you have the KML file of all the coordinates, it's the sort of thing someone skilled in mapping can use to then generate things that look more like the SHP project. It's what I'd recommend starting with, as the skill/time investment is low, it's convertible to more complicated things if you want it to be, and the speed at which you can get something together will make it clear to you whether it is a useful form of analysis/work anyway.

Data visualization has been very hot recently the last couple of years for internet marketers. Very very hot actually. The simplest format is called the infographic, there are some free tools to make them and a lot of people freelancing them. If you are looking to produce something relatively simple for high school or basic college classes this is a low cost or easy to DIY option. Here is a good site showing a lot of different types of infographics so you can get a feel for them, most are simple but if you sift through a bit you can see that some pack a surprising amount of info in a small space. http://visual.ly/

Again, a simpler choice than most, but will have the advantage of looking very familiar to readers, it is a good format for overview type stuff.