Google Maps is great on a Android device, if you have 3G or wireless internet all the time. If you don’t have 3G and are traveling outside, then you need offline maps. One of the best apps for offline maps is MapsWithMe.
The interface of MapsWithMe is similar to Google Maps. Its maps are derived from OpenStreetMap and maps for most cities and countries can be downloaded from inside the app. The maps are in vector format and so are very light. For example, the entire map for Singapore is just 3.7MB!
The rendering of the maps is not as beautiful as Google Maps, but I found it functional enough for use during traveling. From my experience, the transport infrastructure is well mapped, but the information on many popular business destinations can be missing. If you need to bookmark the places you like, you can do so with the Pro paid version of the app.
Tried with: MapsWithMe 2.6.2, Android 4.4.2 and Moto G