A great game I find when it comes to outdoorsy activities isn't a video game, but it's fun non the less. As you walk around outside, find an object that starts with the letter A, then find an object that starts with the letter B, and so forth.

I think a lot of Challenge geocaches fit what you're talking about. Like you might have to find a geocache in every county in your state, and each of them gives you part of the coordinates to a final geocache. Or you have to find one for each Bingo square to get 5 in a row, all in different national parks (I think you can't hide them in national parks anymore, but you get the idea). For different countries, you could do a challenge to find the oldest geocache in 10 different countries, something like that, and I'm sure there are a ton more challenges already like that.

A public transport race? Pick a starting city with a variety of decent public transit options (coach / train / aeroplane etc.). You and another friend meet at that city and have a third friend tell you your target destination, ideally a landmark in another city centre with decent transit options. From the moment you learn where you have to go, you have to get there only by walking or taking public transport. First one to reach the destination wins. Tailor the scope of the trip to your budget and time constraints.