First, I'm jealous! I've been to Moscow twice and loved it both times.
Second, you should also explore the Google Play Store for additional map apps specifically for Moscow. If you can read Cyrillic (which you should at least learn, even if you don't speak Russian - it makes it easier to read road signs and match up to maps), then try Yandex.Maps or Yandex.Navigator. If you don't speak any Russian, there's an app called Offline Maps: Moscow, Russia, that looks to have transliterated text, translations, as well as Cyrillic. It looks pretty good, but doesn't offer turn by turn directions, though does have points of interest, way points, compass, street index and saved map views.
Certainly download one or two of the Metro system guides that map out their subway system. That's really the way to go, especially in winter. Their system looks complicated, but it's actually very comprehensive and logical. As a tourist (and especially if you don't speak Russian), you definitely want to stay away from the gypsy cabs - stick with the legal ones (not as adventurous, but safer).
And of course, download one of the travel guides, like the free Triposo Moscow Travel Guide. They're basic, but offer pretty good information.
By the way, if you have the time, turn off the maps and just do a little walkabout. It's the best way to discover the city. Have fun, enjoy the theater and Red Square (try a Kremlin tour, too), and try to stay warm!
Sent from my Nexus 7 using Android Central Forums