But then I remembered Hexographer, a free Java app that, among other things, will generate a hex-based map for you, using terrain types you specify. It does this semi-randomly, using a random sprinkling of the various terrain types to seed the map, then filling in surrounding hexes based on what's already been decided, and how likely one terrain type is to be next to another.
After generating half a dozen maps and tweaking some of the parameters, I was left with something interesting and characterful, that divided nicely along geographic boundaries into two halves, with surrounding countries hinted at.
The next step was to use some logic to lay in river systems flowing out of the hills and mountains and down to the sea, then deciding on the locations of settlements and connecting them with a network of roads.
Naming the settlements was a challenge. I wanted puns and funny town names, but names deeply rooted in the culture of the country my own states draw inspiration from. So, Baden-Hundsheim should feel Germanic, with strong Turkish influences to the South (more on that later). Formulgala should have a vivid Russian streak. I zoomed in tight on the Austrian-Hungarian border, and on southern Russia using Google Maps to soak up some examples, and started playing with words that sounded right.
The results are shown here. When you're pronouncing the names of the towns and cities, try adopting a stereotypical Russian or German accent. I suspect they're funnier that way.