Love CoMaps, it had shockingly good routing instructions for subway trips in many European cities that I visited, and saving the maps locally let me navigate with ease before I picked up a local sim card. I don't find it very effective to search by address, but landmark or business name work well. At home I just have my usual destinations bookmarked and it has solid routing instructions, though it doesn't have live traffic updates because it doesn't connect to any remote servers.