Do you reject the notion that architecture can be art? What does Fallingwater say about the human experience? You can argue that it argues that humans should live in aesthetic harmony with the world around them, I suppose, but it seems a stretch to me. You can argue that it's pure craft, not art, but I'd disagree.
What does Sarah Winchester's house say about human existence? Well, you can pull any of a dozen interpretations of the "thing" in its historical context, depending on what "facts" about her life that you believe, but the house itself is a thing separate from her life. If you strip away the "mystery" of her life, it's just a house that does non-functional things. As such, I think it is art -- accidental art, not something that was controlled all the way, but art nonetheless.
Back to games: Dave Theurer, a designer from when game design was something programmers did while coding, created games that came out of his nightmares. Tempest, though taken to be a sort of standard "shoot the space invaders" game, is "about" trying to repel a horde of alien-but-native creatures from within the earth, creatures that will grab you and pull you into the darkness. If that's not a fundamental meme of human art, I don't what is.
Missile Command was inspired by his nightmares of nuclear blasts annihilating his home and himself. Surely the scenario, that you can't win, that you can't counterattack, that you can do nothing except temporarily stave off extinction, and that you know there are humans on the other side of the attack, says something about the human condition? It's as conceptually deep as, say, "Miracle Mile," at least. (You can say that arcade games of the time seldom had an "end", but Theurer's interviews state that he rejected the suggestion by management that it have an ending because nobody could really win a nuclear war.) By your criteria, is this art?
I think you're getting hung up on the narrative issue, given that this conversation is coming from film and literature. But who says art needs any narrative? Is there a need for a narrative in order to appreciate Church's "Cotopaxi", or Bosch's "Ship of Fools"? There are contexts to them that inform a viewing, certainly, but don't they stand on their own?
Admittedly, most narratives in games suck very badly. I can't play most JRPGs anymore for that reason, and I've never been able to get into any western fantasy-influenced games because of the ludicrous stupidity of it all. But narrative isn't everything. It isn't even the main focus of a game. It's one aspect of a complete package that also includes music, visual design, control of character(s) in a miniature universe created by humans, etc. Much as film integrated script, visual design, and music, games integrate those and more.
I expect that the concept of games as art will have a longer gestation than film. After all, film could piggyback from stage, already an accepted artform. Video games have as their antecedents: movies and their ancestors; formal logic puzzles, ala Lewis Carroll; formal abstract games, like Go, Chess, and card games; and "human" games, such as hide'n'seek, sports, and debate. These are not like forms, and a form that integrates them is going to have major growing pains. However, whether or not you believe that anything has yet done so successfully, it is foolish to deny that a form that amalgamates these unlike forms has the potential to be art.