I don't agree that the data set would be much smaller. Maps for driving may look complicated, but they're just weighted graphs. You might have a few different data points for MLK drive like length, average traffic, speed limit, class of road, etc, and these values might even be given for each short stretch of the road, but you don't have to have any knowledge of the actual topography, and all of these values can be safely taken as rough estimates. No one is going to die if you falsely classify a stretch of road as high traffic when it's really moderate.
For a submarine, you need to know the topography of the sea floor down to meter scales. Accurate maps are few and far between, and difficult to create. Changing currents, underwater landslides, silt from rivers, sunken wreckage and even just garbage can create and move obstacles large enough for a submarine to care about in relatively short timeframes. Of course submarines can and do navigate with maps prepared ahead of time, but it's tough, and every now and then you get a run in with a sea mount.