This is a topic I've done before, but this is new content.
Space in games is usually used both to separate/pace challenges and to form the challenges.
This is controlled mostly by the algorithms which control the space. For example, the simplest spaces are probably in adventure/text games, which have clearly defined rooms and very basic movement control. The gameplay in such games is less about navigating the space and more about putting non-space-related things together. However, even in that sort of game, everything is couched in space. You move to rooms to try things out, and progress is measured in new rooms that you can explore.
Most games have more complex spatial algorithms which allow for correspondingly greater amounts of gameplay in the space, rather than adjunct to it. Most games are about exploring space, and most of the rest are about modifying it, but that's a false dichotomy. An RPG is mostly about exploring, while Sim City is mostly about modifying, but an FPS is both. There is no "real" difference between exploring space and modifying space, because exploring space can be thought of as modifying space such that your avatar is in a different location. Obviously, a player might not feel that way, but I'm talking about underlying algorithms and rules.
A fog of war over some terrain: are you exploring the terrain as you vanquish the fog of war, or are you modifying the terrain to not include the fog of war? It's a useless semantic question. The algorithm of the space allows the player to vanquish the fog of war. There is no need to consider whether it's exploration or modification unless you're considering player psychology.
Well, there's no fundamental difference between space that is explored and space that is modified unless you're going out of your way to create one. But what about space where the rules change? What about once you get that double jump?
There's no fundamental difference then, either. The algorithm that governs when and whether you can double jump occupies the same "logical space" as the rules governing how fast you fall, whether you can survive an enemy's gunshot, whether you are stopped by a wall, whether you can build a house, and so on. It's a complex logical space with a lot of complicated rules, most of which are inherited from earlier games in the same genre.
Many of the most memorably original games are original because of this logical space, rather than the tangential rules governing things like XP, inventory, etc. Braid and Sands of Time both included time mechanics that gave you a strong and then-unique method of navigating space: they did this partly by simply altering the mechanics of what it means to mis-jump or die. Additional rules, especially in Braid, added additional layers of spatial complexity.
Games like Shiny's Messiah or Omikron Soul give you the power to switch bodies. While this often doesn't change the mechanics of exploring space like rewinding time does, it does change where you can go and what you can do when you get there. Which is in the same logical rule space.
Even games which aren't avatar-centric, like Tetris or Guitar Hero or Bust-a-Move, still use this logical space to define the core gameplay. There's a "space" that follows specific rules, and you move forward by interacting with the space correctly.
It's clear just how far this logical space can bend. The same basic idea - the algorithms that govern interaction with space - can be used for everything from Braid to Tetris to Sim City to Quake. Tangential rules are then added to govern the progression of these algorithms and spaces. You move from stage A to stage B. You select an avatar and a map. You get a new gun. You earn a new skill.
Even in a game like Skate, where the whole game is about interacting with space, there are still tangential rules: buying new skateboards and clothes, accomplishing arbitrary tricks and times. These tangential rules are often what designers agonize over.
I prize the spatial interactions. They are usually the fundamental interactions. When a player presses "right", the immediate response is the avatar moving right inside space. This tight, deep feedback can be found in most really great games: they're really great because they enhance the experience of interacting with space. Even the RPGs we prize are largely prized not for their RPG mechanics, but for their spatial experience. How pretty? How impressive? How interesting is the space we're in? Is the narrative tightly tied to/represented by the space?
What do you remember about FF6? The characters? Do you remember why you remember the characters? Because they defined themselves with space. Kefka burned down a city, then burned the world. Each character, on their own, had representative game levels - castles, small homes, smoky gin joints, vast plains. The characters were tightly associated with the spaces that represented them.
In games where exploring space is more tightly done, this is even clearer. Can you even name a memorable action game that didn't include some extremely well-polished or unique aspect of interacting with space? If you can, you're probably not remembering the interaction. Half Life 2, for example. The interesting aspect was not the gravity gun, which was barely a curiosity, but the level design, which forced very specific pacing on to the player. Did you notice that while you were playing?
Now, with that said, has a game ever become lauded for its tangential rules?
Can you name a game where the game was famous because of its inventory wrangling? Its level-up mechanic? Its deep social interactions?
It's hard. There are so few. A few that leap to mind are experimental games, famous only because they're trying out some weird new algorithm. When it comes to real games - even indie games - those tangential rules don't seem to add much to the final product. With one exception: when the tangential rules allow you to modify the spacial rules. For example, a level editor.
Which kind of feeds back into the original point: it's all about the space, and the algorithms that control it.