You could make yours a Geocaching app with fog-of-war. They've got an API for third-party apps too, so it should be easy enough to develop, and actually fun to play.

If you're feeling ambitious, add some RTS elements like from Age of Empires - eg if you add someone as your ally, you can share their line of sight. Finding certain types of caches, or POIs, increases your resources (gold/stone/food/wood - maybe visiting Pizza Hut gives you extra food lol). And with these resources, you could build virtual structures like castles etc. Other players could spend resources to take it down (but they need to be physically at that location), and you could spend resources to defend your building.

Kinda like Ingress basically, but with medieval/RTS elements and geocaching thrown into the mix. How's that for a challenge? :)