Seek NYC
SeekNYC is an exploration game in which you uncover a map of New York City and can get recommendations to discover something new outside of your uncovered area.
The app tracks your movement as you trek through the city and reveals an underlying map. It shows you what percentage of the five boroughs you've actually uncovered.  You can choose between 4 different colored skins for the map overlay and just shake your device to generate recommendations for exploring places off your beaten path.

Available for download in the iTunes App store