This is such a neat question. But I think I have to reframe it a little. I don’t like doing this, but I don’t think I have another answer.
I don’t think this magical feeling is specifically a matter of player agency. I think it’s about discovery, and not being able to see the limitations of the world. In a parser situation, this manifests as the feeling that This thing will respond to anything I type into it! because responding to input is kind of the only thing a parser game can do.
But other formats have other tools. In Super Mario 64, you can put the controller down to get a snack, and come back to find that Mario is now lying on the floor, mumbling in his sleep. You can accidentally brush against a brick wall and notice it rippling like water. And you think They didn’t tell me that could happen. What other tricks are in here?
In Super Mario 3D World, you can notice what looks like a giant golden train off in the distance, and wonder What is that? How do I get there? Can I get there? You can reach the last part of the map, defeat Bowser, and then discover that actually that wasn’t the last part, and there are a bunch more levels to try. You get to think Good grief, how much game is there in this game? What else am I missing?
The magical sense of possibility arises from these moments of discovery, and, this is kind of tautological, but these moments of discovery arise from the game not telling the player everything. It’s very easy for a parser game to give a complete list of all the verbs it recognizes, dismantling the possibility for the player to try a new verb and get a surprising response. Similarly, Super Mario 3D World could give you a list of all its levels and draw out every detail of its structure on its map screen—but it doesn’t. It lies to you.
(I should also mention Red Dead Redemption 2, which produces this never-ending stream of neat details for people to find. I think the fanciful notion that “The world simulation is keeping track of literally everything” is kind of the same thing as “The parser will understand literally anything I type in.”)
And so the answer for creating this magical feeling, in any kind of game, is to add a bunch of cool stuff and let players find it on their own. The more neat things they discover, the more players are forced to wonder Where are the limits of this world? And now the world feels infinite.
I think the problem with creating this feeling in mainstream games might be more cultural than formal. There’s a very powerful impulse for people explain how to get all the endings, record the locations of all the collectibles, and post an exhaustive list of easter eggs. (You can listen to me repeat this one basic idea over and over again for about half an hour on Extrasode 3 of this podcast.) IF also has this problem to some degree, plus the fact that it’s so easy to decompile a game and snap the neck of any mystery it might have contained.
But you can try to preserve this sense of magic for yourself. You just have to be okay with not knowing everything and seeing everything.