For a concrete example, I'll nominate the very first video game I ever played: The Legend of Zelda for the NES. This is by no means an easy game, however, so I'd alter the win condition: you don't need to beat the whole game, just collect a single piece of the Triforce.

As a kid I was able to gather the first 6 pieces of the Triforce without any outside help. I think an AI should be able to get at least one, given that it's playing a video game for the first time.

As for the "embedded knowledge", I'm happy to talk about context in terms of cultural references, heroes, the monomyth, etc. The Zelda series draws heavily on these concepts, though I am not sure how much I knew of them as a 6-year-old.

I'd say a really simple game like Pong or Snake would already be enough. Only two(or four) possible inputs, simple graphics.

The difficulty could also be decreased, but in the end the challenge would be to grasp how the game works, not to beat highscores.