Many good video games have a feature that I call "novelty progression". As the player advances through the game, they are continuously introduced to new experiences that are outside of the core game experience. One form of novelty progression is "feature progression" in which the novelties will change the core game experience.
As an example of a game with novelty and feature progression, consider Starcraft's single-player campaigns. You begin the campaign with a small number of units available to you and new units with new abilities are unlocked as as you progress through the game. You continuously encounter new environments and new enemies, and you are given an unfolding story with new characters and new twists. Furthermore, every stage has something different from the core game in terms of gameplay. There are scripted events, a timer, hero units with spoken dialogue, allied units to rescue. Several missions only give you a small tactical squad and no base with which to produce additional units. None of these changes to the gameplay are overdone to the point of being considered a normal part of the game. Once you beat all of the missions and become used to one of the races, you start over with a second and then a third race whose strategies are different.
What makes novelty progression work? First, there must be a solid game core that is fun to play without the novelties. The novelties must be new and not something previously seen with a different skin. Also, with so many games having been produced, novelties must not be the same thing that the player has seen before in many different games unless it is done well in a new way. A desert level or an ice level might have been awesome in its own right in the 1980s, but today you will have to add something special.
What makes feature progression work? The new features must be useful, so that you can use them in more than one place. They must be more than keycards. Also, new features must not break the game unless they are added near the end.
The Metroidvania category of games are based on feature progression. Get the item that makes you jump higher and you can reach the next cave. Get the item that lets you swing around and you can reach the next cave. Get the item that lets you blow up barriers and you can reach the next cave. As already mentioned, feature progression works best when you can use these features in normal gameplay.
The Legend of Zelda is worth mentioning in terms of feature progression. Of the many items you get, you can use many of them in normal gameplay but generally half of them are not very useful outside of the one place where you need them. However, very few of the items are totally useless in normal gameplay. In the original LoZ, the fire, arrow, and bomb were usable in normal gameplay but had enough drawbacks to not be worth using. The programmers got around this drawback by providing enough places to use these limited-use items to make them seem more useful to the player.
There have been some experimental Flash games that are based on feature progression (or progressive feature removal). One that comes to mind is Tower of Heaven.
RPGs are based on novelty progression with their storylines, environments, NPCs, and enemies. They also have some feature progression in that as the game progresses you get new abilities with new effects that may change your decisions in battle. This feature progression has tended not to work well even in big-name games because the new features either are game breakers or are degraded to the point of uselessness to prevent them from becoming game breakers. Game developers also have a tendency to introduce all of the classes, elements, and status effects early in the game or by the midpoint rather than progressively introducing them a bit at a time throughout the game. This may be justified by certain features of RPGs being subtle enough, with calculations based on many factors, that the player might not notice some of these features unless an early tutorial introduces them.
What happens when a game has a good core but does not have novelty progression? You get the RPG trope "You must collect ten blue ratsasses" where you keep getting assigned the same task with a trivial difference. You get the Arkandian game series in which there's a very nice RPG engine but every event is the same and you've played out the game in fifteen minutes, after which you're only raising numbers for the next ten hours until you reach the end of the scripted content. You get bored, and that is the ultimate condemnation of a video game.