Think about what the purpose of such a map is. Medieval maps tend to fall into three categories:
- road maps
- coastal maps
- maps of the world
If it's for pilgrims and merchants traveling by road, it'll have all the major roads marked, along with inns and convenient places to stop to water the animals -- and it won't describe the wilderness or the sea at all. Take a look at the Tabula Peutingeriana for an example of a classical/medieval road map.

If it's for seafarers, it'll have all the harbors and rocky shoals marked, along with notes about winds and whirlpools in the sea. It won't say anything about what you'd find further inland. Take a look at some medieval seafarer's maps, called Portolan charts.

If it's a map of the whole world, it'll try to include all the regions that the mapmaker has ever heard of. The areas near home will be fairly good, but the further away you get, the more vague and fantastical you get. Take a look at any of the Mappa Mundi and see how Europe and the Mediterranean tend to have all the right parts, while India and China get pretty speculative.

Modern maps often aim for somewhere in the middle. All the maps above are of the same region; now take a look at how Google Maps renders it:

This map doesn't tell you how long it takes to get from one town to another, it doesn't tell you anything about the bays and harbors, and it doesn't even show rivers at all. If you're looking for those features, one of the medieval maps would be better.
What the modern map does well is getting the features in the right place compared to each other. The medieval road map might tell you exactly how long it takes to get somewhere, but the modern map tells you exactly where it is.
A traveler doesn't need to see every little kink in the road or every administrative boundary. They need to see how to get where they're going.