Depends on the genre really. For action/action-adventure/rpg games in general, it's by far the combat mechanics/battle system. I can't point my finger on my favorite aspect of shooters though. The atmosphere and soundtrack can also greatly increase my enjoyment, and so can the visuals - both on a technical level or with an interesting art style (e.g. Okami).
Story is the thing I value the least. I can easily go back to a game with a terrible story and great gameplay, but not the other way around - Grandia 3 is one of my favorite rpgs, and the plot is really silly, for example. I see the plot as nice bonus rather than a requirement.