It wasn't long ago that going on holiday entailed purchasing or borrowing a good map book. Now that a smartphone fulfils our navigational needs, you still need to find the most suitable app, one that works without a data connection, can provide spoken route instructions, and directs you to the smallest of pedestrian paths. On Android, three free apps used in combination provide everything you could want.
When you have a data connection, wifi or mobile data, Google Maps has a good offering. However, its offline facilities are perfunctory. You can only designate certain small areas to store, which expire after 30 days unless manually refreshed. It doesn't store all details, and often decides to not show road names. It also doesn't allow routes to be calculated, though you can ask for directions whilst online, and continue to follow them offline.
The previous champion of offline mapping apps was Nokia's Symbian app. Now that Nokia has been swallowed by Microsoft their mapping unit has reappeared as Here Maps. Although it has only been on Android for a few months it is already a mature product. It allows the downloading of entire countries, and has full offline searching and routing. Occasionally its searching is not up to the standards of Google Maps, and obvious searches fail or landmark locations are indicated some miles away from their actual position (ahem, Buckland Abbey, ahem). This might, one imagine, lead to some unwarranted criticisms of the human passing on the Here Maps information to a driver attempting to reach said place before closing time.
If Here Maps is not sufficient, and you want more detail, then the final app in your repertoire should be OsmAnd. This uses the mighty crowd sourced Open Street Maps data, and can be fully downloaded for offline use. It offers offline routing and comprehensive searching. Its interface is less polished than Here Maps, and when driving it doesn't offer speed alerts or speed camera warnings, as Here Maps does. However, it seems it holds the knowledge of every item of geography you could ever want. Its search never failed us. More than that, for keen ramblers, it displays almost all footpaths in existence, exceeding even those known by Google Maps online. When you're two hours into a trek through the wilderness of Dartmoor following vague written instructions and passing an average of one human and ten wild ponies an hour, it's reassuring to see that your route is following the dotted red lines of OsmAnd.
With free mapping apps, using more than one you can get the best of all worlds. The only problem is that each app will want to store its own maps, which can add up to a large amount of storage, but storage is getting cheaper all the time.