The "perfect game", doesn't and will never exist. Not for everyone.
However, the "ideal" game, quite honestly, must contain a bit of all those categories. To a certain degree.
A good story with interesting characters is meaningless if your setting, sense of atmosphere (immersiveness), and ambiance are bland and uninteresting. Likewise, all of the longevity, quality narrative, and ambiance in the world become worthless if your controls are slow, unintuitive, and clunky.
An ideal game will have a good balance of quality narrative, good characters, unique or interesting mechanics, believable or fully-realized setting, decent (but not over-drawn) longevity, and solid controls.
One aspect can be weaker than the others, but only if the others are better for it. Though, one aspect failing on all accounts negates just about any positive points of the others.
So, to answer your question, a "perfect game" will have all of those things.