The grid issue sounds like an American problem. In the UK, maps are derived from Ordnance Survey maps and carry the OS grid, and our GPS units can be set to use the same grid and datum. I've never seen a topographic map which didn't have the grid squares, and I make sure my road maps have it too. The UK is a small country so it is relatively easy to produce good maps for all of it.

(I bought my first GPS unit a few weeks ago, so I have just recently learned about how they interact with maps. Here we are usually advised to set GPS north to grid north, rather than magnetic north or true north.)