For the past twenty or so years, I've been thinking about exploration games. I've created hundreds of prototypes and several tabletop games about exploration, so it still irks me to see video games that drop the ball.
Let's talk about specific techniques to make exploration gameplay fun.
For starters, flow is absolutely critical in this kind of game. Your goal is not to reward the player or keep them interested, but to keep them in their flow. Unfortunately, flow varies over time and all players are a bit different.
So 1) establish flow and 2) keep the flow flowing.
1) Establish Flow
Establishing flow is tricky, but to me a big part of it is letting the player smoothly adopt a variety of short- and medium-term goals, discarding and rearranging as they see fit. The problem is that most exploration games start off with "here's a three hour tutorial".
Well, here's three hours where there's no flow state.
Every time you interrupt the player unexpectedly, every time you tell them what to do, you're resetting their "flow counter". On the other hand, if they don't see enough implicit short- and medium-term goals, they can't start their "flow counter". So both are bad.
My focus when I create exploration prototypes is to create a lot of easy-to-grab short-term goals that lead into medium-term goals quite naturally. New players will grab at the obvious short-term goals and, in the process, learn medium-term goals.
For example, if you start up No Man's Sky, the first thing you'll notice is that there's a space ship. This is an extremely obvious short-term goal. The sparking engines also clearly show a medium-term goal: fix the engines. Debris, tall plants, glowing plants - these all give the player short-term goals and, in the process, they learn about resources and loot.
Unfortunately, No Man's Sky falls short in a number of ways aside from that. It takes a long time to figure out how to use resources, and it's easy to run out of power before you figure out how to restore your power. Inventory management is obnoxious and opaque. This isn't a tutorial failure: it's a fundamental design failure.
It'd be fun to talk about How I Would Have Designed No Man's Sky, but in the end the point is simple: don't have popups. Don't have a tutorial, don't have early-game achievements, don't have an integrated crafting menu or complicated fuel management.
Focus on having delightful short-term goals (glowing plants, chunky debris, space ship) and a variety of short-medium-term (mine-able obelisks, minute-long walks) and medium-term (ruins on a nearby continent, requiring 300 ore to upgrade) goals. Experienced players will automatically balance this stuff out with long-term goals, but newbies need this stuff to flow naturally and easily in layers.
2) Keep the flow flowing
"Flow state" isn't one permanent thing - players constantly shift gears, and all players shift at different times depending on their personal preferences and mood. Because of this, any game that focuses on keeping a flow state needs to allow the player to shift their play whenever they want to, and lower that barrier as much as possible.
The two pieces to this are opportunistic short-term goals and floating medium-term goals.
Opportunistic short-term goals are easy enough: while you're on a medium-term goal, there should be a variety of opportunities to do small things en route. For example, seeing and harvesting good resources while running along, or seeing a hazard in your way and having to route around it or endure it.
Be careful about getting too aggressive: the player should choose how deeply to engage with the short-term goal. Forcing them to fight or trapping them in a deep cave is just distracting. Those kinds of forced engagements can come at the end of a medium-term goal, though, as a finale.
The point is to let the players choose to do a few fast-cycle loops if they want to, because they may be wobbling towards the fast-cycle part of their flow.
Floating medium-term goals are the opposite. When the player finishes a medium-term goal, they'll choose the next medium-term goal based on a lot of criteria. One of those criteria is what they feel like doing next. So try to engineer it so they have a few very different medium-term goals. Basically, some that will push them to walk, some that will push them to fly, some that will push them to warp, some that will push them to build - whatever varied gameplay you have.
Coming up with a variety of classes of medium-term goal is critical to this. In general, I define a medium-term goal as something with several opportunities for short-term goals along the way. So you can set up your medium-term goals to allow the player to choose what kind of play mode they're going to enter and what kind of experiences they're going to have.
For example, many medium-term goals are about traveling for less than 10 minutes to a known destination. But others might be about hunting for a specific resource, one which can only be found in a particular play style. Other medium-term goals might involve setting things up properly to survive a new class of environment, or caring for a pet, or buying something from a distant shop, or anything else you can think of based on your available kinds of play.
As long as there's stuff to do along the way.
Allowing the player to fluidly "change bands" means the player can stay in their flow state for longer, since as their mood changes, they can change their play.
3) Long-Term Structure
Exploration games have a few fatal flaws, but one of the big ones is that they're typically crafting/base-building games. By default, neither of those styles of gameplay actually makes sense for exploration. Exploration features a random mishmash of results, while crafting requires specific inputs and base-building typically locks you down to a location.
Base-building is largely a solved problem: either allow the player to take their base along, or allow players to revisit their built bases quickly and easily.
But crafting is still an issue. NMS shows this flaw in spades.
Because launching into space requires about six different resources (worst case), that means every planet must have those six resources within walking distance at all times. This leads to planets all feeling the same, even if they have wildly different visuals.
There are some simple techniques you can use. First off, make basic movement rely on no more than one resource (perhaps zero resources). If the only thing required to get into space was hydrogen, great. Every planet can have hydrogen on it, perhaps in different forms. The rest of the resources can be radically more scattershot.
A fantasy exploration game might require you to eat once in a while, but you can eat almost anything. Every biome just needs to have something vaguely edible in it.
Another simple technique is to use categorized resources instead of specific resources. IE, rather than requiring iron specifically, you could use any structural resource. Rather than requiring plutonium, any energy resource will work. They can have different stats, but any of them can get your crafting off the ground. This means that rare resources can fill the same slot as common resources, just be substantially better in some way.
Moreover, this allows for transmutation recipes. For example, if you just need to have any structural resource, you can turn oil (a fuel resource) into plastic (a structural resource) using some kind of machine.
The idea here is that the player is almost never "stuck" on a particular resource. They may get themselves stuck by insisting on using a specific rare resource if they like, but the game never says "you can't build X because you didn't find any copper". You can substitute in a variety of materials instead, including converting unsuitable materials via some time-consuming process.
This means the player is free to explore. When they find Xenocite, sure, it's just another structural element, but the resulting stats are off the charts. Build an engine turbine out of this, it'll be able to withstand immense strain and therefore you can go ten times faster than the same turbine built out of iron. Same thing, radically different parameters.
This also means you can let the player be isolated. You don't need a universal market everywhere, you don't need every resource everywhere. Let the player feel like they're out in the boonies or someplace super rare and weird.
Construction is also easy to tie into this, if your game has more than simply crafting. Bases made out of many different materials will all feel radically different and have different parameters. Just remember to solve the "base is left behind" problem.
4) Create Meaning
Exploration needs to have meaning to the player in order to make it fun.
A) Make it gorgeous. If the player wants to take pictures, they'll want to explore. Don't forget the audio.
B) Connect it to existing meaning. NMS has dinosaurs and trees, both of which are familiar and carry meaning already. Their alien species also feel familiar, callbacks to things you've seen before. Similarly, many of the stories are vignettes that simply tug on existing meaning - IE, a terrified warrior asking if you'll help him run away.
C) Chains of content. You can create meaning by making pieces change over time. For example, helping person A will make person B attack you later, or whatever. This is easy to script, but randomly generated chains need to be done carefully because the player will quickly start to categorize them and their deeper meanings will vanish.
D) Personalization. Allow the player to customize things (recruit friends, build bases, etc), then subject them to a variety of threats that test fitness and pull the player into defending the weak elements. The player will automatically feel strongly about something they own, so threaten the things they own. Just... not on a timer. Timers will break their flow.
E) Multiplayer. Allow the player to share things with other players and make it seem amazing. For example, screenshots and videos should inherently vary from player to player so that any player should think they have something unique to bring to the table, even if they're a newbie. Of course, sharing blueprints or seeding other player's content are also good opportunities to draw players in. This creates a bevy of medium-term goals as players strive to create/replicate something amazing.
Anyway, those are my thoughts.