To the OP, you are thinking in the right direction, but you are not going far enough. What are video games really?
A lot of people get caught up on the relics of the past when thinking about this, and games, being inherently complex, can be a lot of things to different people. So games can be arcade games (personal challenges where you try to beat something, be it a boss, or your previous high score), I happen to think From Software games fit into this mold recently, or they can be replacements for traditional sports (e-sports, League of Legend, Counter Strike, etc), or they can be time wasters for adults, or they can be puzzlers for the intellectuals, or they can be C&C toys, or they can be dungeon crawlers for the autistically minded, and other things.
But all of these things can be done in other media/venues. You can play chess for challenge, or play basketball outside, or some wargame/PnP game with your nerd buddies. What can video games let you do that nothing else can?
They are the ultimate form of escapism, letting the player experience an alternate form of reality (in a much deeper way potentially than books, movies, etc). They are like a simpler version of the universe itself (which is itself likely a video game-like simulation), letting conscious beings experience things beyond their current life limitations (e.g. some programmer nerd or construction worker can be an Emperor or a Wizard or a medieval knight or whatever else).
So yeah, ultimately simulation is the only thing that matters in terms of achieving this highest holy grail of gaming, because it can create everything else. This is why Dwarf Fotress, given another 30 years of development if things go well, should be the greatest game ever made at some point. Great combat and exploration can emerge organically from a deep enough simulation. And to answer your musings about the place of narrative, a deep enough simulation can cover that too. The goal of DF, for example, is to eventually procedurally generate random equivalents of Lord of the Rings or Game of Thrones. But until then, a good human made narrative can help bring the world to life. For example, the Witcher games don't have the greatest gameplay and they are not very deep on simulation, but the great writing/characters/quests make the world feel like a place you want to get immersed in, while Larian games, full of simulation though they might be, have such vomit inducing writing that it ruins any wish for a normal person to be lost in them.