Something that rewards exploration, presents puzzles that aren't there for the sake of impeding your progress, but to make you think of the entire scenario, encouraging you to experiment with newfound skills to overcome obstacles, and has the ability to still be engrossing on subsequent replays.

(Currently replaying Twilight Princess GC btw)

Great gameplay is paramount. Everything else can vary depending on the game.

Advanced graphics aren't important in a game like Tetris or Picross, for example.

Uncharted wouldn't be the same without a well told/acted story, but keep lengthy dialogue out of my Mario games.

These types of things are on a game by game basis, but the one thing that remains constant for me is that the gameplay or user interface must work well.

So yeah, I guess being fun/compelling is my answer.

depends on the genre
My perfect game is 3D Zelda and 3D Mario

Narrative

Player Influence

Gameplay

Quality Presentation

Challenging in some way (be it through tough difficulty options, puzzles, clever AI, etc)

Customization/Progression

Compelling characters

Multiplayer (not always a must, but let's face it, almost everything is better with friends)

Graphics are nothing but eye candy. They are the last thing on a scale of importance to me. Gorgeous graphics can be nice, but then again, what is the barometer for "gorgeous"? To me, a lot of NES games and other 8bit games are still to this day great looking. Whereas many modern HD games, while technically advanced, kind of look like shit to me. For a lot of people, "realism" (with a heavy accent on the quotes), seems to be the water mark of graphics being "good" or not. Not to me. "Realistic" graphics CAN be great. But to be honest, a lot of different games made by many different developers these days, all still wind up having a very similar and to be frank, generic look to them, as far as I'm concerned. The trope about "grays and browns" is a bit tired, sure, but it's also rather true.

I appreciate developers who actually bother to create their own unique art style. Who put some COLOR into a game, not necessarily "Cartoony" (Though that can be wonderful if done right), but just....I don't know....actually TRY to give a game it's own visual identity. Like the 2008 Prince of Persia game. It had it's own unique look, not quite "cel-shaded", almost more of a 3D comic book type visual. But I liked it.

But beyond graphics, the most important things to me in a game, are Gameplay, is it FUN to play, does it CONTROL well, etc., and Content. A great story or setting in a game can be awesome, but I don't need some wannabe Hollywood (or rather, direct to video) cinematic experience. A game's soundtrack is important, but history proves that game music can be amazing WITHOUT having to always be expensively done orchestrated movie score type material. The core gameplay and the amount and type of content a game has, are the most important, fundamental elements of whether a game is "good" or not, as far as I'm concerned. A game can have very simple, basic, even "bland" graphics, but can be incredibly fun to play, and thus it's a great game. Whereas (and this is proven a LOT these days) a game can have the most gorgeous graphics you've ever seen, but NOT actually be all that fun to play, and certainly not have any real replay value once you "beat it to see the story".

And to me, that's the problem with where the video game industry is going these days. Don't get me wrong, I'm a writer myself, and as already stated, a game having a GOOD story is a bonus. But that also seems to be the focus these days, being "cinematic" and having some (often feeble) attempt at a deep, elaborate story. A game can be pretty and even have an interesting plot, but if it plays like shit, it's still a shitty game. And that IS often the case, more often than it should be by far. To me, you shouldn't be playing a game solely for it's story, OR it's graphics, and "beating the game to see the ending" shouldn't be the whole focus of why you're playing. Video games used to be about the EXPERIENCE you're having while you're playing. Getting to the end and seeing whatever ending might be there (or not), was secondary, a nice cherry on top. But it was JUST the cherry on top. Now, it's the whole fucking cake, at least as far as I see in a lot of modern games. And that should never be the case.

You should play the game for the gameplay, to get lost in a virtual world and have FUN in it. Not to get from Point A, to Point B, to Point C, to Point D, etc. etc. etc. ad nauseum in a straight-line sequence of Quick Time Events and Cut-scenes. THAT, to me, is not a video game, and not what video games should be. That isn't to say there isn't ROOM for that type of game to exist. BUT, it personally makes me very sad, and even a little sick, that that is what a majority of especially these "AAA" blockbuster titles, in an industry driven solely BY those titles, has become. Which is why I appreciate companies like Nintendo, to some extent Sega, and a handful of others who still have a sense for what USED to make games good. And while they don't totally embody that "old school" approach, I will give Bethesda some credit in that category as well, because for ALL the stupid (and unnecessary) bugs and glitches and problems their games have, things like The Elder Scrolls do, while having a "AAA" package, still seem to at heart put the gameplay first.

It's not a matter of nostalgia (the poor-man's straw argument to whip out anytime someone brings up how great things used to be versus today). It's a matter of gaming principles, and priorities. A handful of companies still have those priorities straight. But many, I think, do not. Developers need to cut the mega-budgets, and focus on making games that are actually FUN to be physically playing through. Gameplay should not be a secondary background thing you have to do to get through a story. It should be THE focus, with everything ELSE, graphics, music, story, etc., as GARNISH, supporting and enhancing, ADDING TO the gameplay experience.

I will use OoT to describe my criteria:

. Excellent story and difficulty progression.
. Leaving things for the imagination of the player. (Silence, echo, mist, mystery)
. Excellent Sound.
. Enchanting music.
. Great visuals.
. Fun and inventive items.
. Imaginative locations.
. A good balance of colors (not too dim, not too colorful)
. no blood.
. Secrets!

That's a question with a lot of variables.

I grew up with reading as my primary hobby, so I need for most games to engage my imagination to some degree. A quality plot, good storytelling, compelling characters, and interesting dialogue are all positives. I can deal with a game that has a mix of good writing/mediocre gameplay more than I can most games that have good gameplay/mediocre writing. It's the way I'm wired. If my imagination is just sitting there turning into jelly, I'll probably be bored and find something else to do.

There are some exceptions. Games with a high degree of strategic gameplay that demand your full attention are awesome. I play chess on my Vita pretty much everyday, for example, and I love games like Final Fantasy Tactics. My imagination might not be engage during the gameplay but my brain is working. I consider games like Gran Turismo to be in that same category, as racing can be very strategic and immersive.

I like RPGs and tactical RPGs such as Suikoden, Final Fantasy, Dragon Age, and Valkyria Chronicles. I like sci-fi FPS games like Fallout 3, Borderlands, Portal, and Killzone. I like Gran Turismo and AudioSurf.

I don't like shallow platformers where the story is an afterthought. Mario bores me to tears. I don't like military shooters or most TPS games.

Hello brother. You're one of the few on here that are similar to me in this regard.

Depends on the game and genre, but in general I expect good and fun gameplay. I can live with a game with a bad story (or no story at all) but not with a bad gameplay. 

But to make an amazing game you need all things to be good: gameplay, story, sound, art style, etc. If you can make all those things good then you have yourself a great game, and most of my favorite games of all time fall into this category. And like I mentioned before out of those things the only thing that I can't stand is bad gameplay, but if the gameplay is good and the other aspects are just "meh" then the game will just be average for me.

There's only one exception I can think of which is 999, the game has a meh gameplay but the story is so freaking amazing that it really doesn't matter, although that might be because you spend 90% of the game reading and not actually playing, which in the end makes the game more like reading a book than playing a game.

I hesitate to categorise specific things that must make a quality video game; most of the best games I've played go beyond the sum of their parts and so breaking them down into pieces doesn't capture the whole picture, or do the game justice. 

I also find my appreciation for the things people list in these threads to vary wildly from game to game, making it impossible to rank them in any order either.