When my wife and I did a tandem tour in the Czech Republic this past spring, the tour company set us up with a map book (it was in German but the maps still worked fine), a cue sheet, and a GPS. They specifically only use GPS units that don't have maps. They program in all the way points of the route so you can tell if you are headed in the right direction, but the maps and cue sheets were much more useful. I had the map and GPS up front so I could get the big picture, and my wife would read off the cue sheet so we could follow all the detailed directions. Worked out great. Since we were riding on our own, they also gave us a cell phone with their phone number programmed in so that we could call in an emergency (I'm happy to say we never needed it).
Glad you were able to still have a good time. Now you have maps of the area and can plan your own routes for the next trip!