Have I missed something here? What's wrong with maps? GPS can be useful occasionally for micro-navigating if you're on minor roads where the junctions aren't signposted, but otherwise it's an expensive piece of kit with only a very small display area, and then needs to be charged up - itself an extra logistical problem on a long tour.
In the UK I buy one of those large-size road atlases that come with a spiral binding, and tear out the pages that I will need for each trip. For a 100-mile ride I rarely need more than 3 sheets of paper, that can be folded up so that the current one is on top. I then put these in a plastic wallet, which is either attached to the bar bag if I'm on my tourer, or in a hiking-style map wallet if on my fast road bike (and I've worked out a way of winding the cord round the bars so that it stays in the right place, though plastic zip ties would probably help too). OK, you have to refold / re-order the maps every 50 miles or so to get the right section on top, but that's not a big deal.
You can often pick these atlases up for less than £10, and last year's ones can be got for far less. I've been using the same one for about 5 years but the folds on the Midlands and Wales pages are getting a bit thin now!
In other countries I try and find the map that gives me the best match between scale and readability depending on the distance I'm planning to cover. I often cut the covers off, and they work like the tear-out pages that I use in the UK.