1) 0 - Character Advancement:
2) 0 - Combat:
3) 0 - Items and Equipment:
4) 0 - Story:
5) 0 - Exploration:
6) 0 - Quests and Puzzles:
Secret Quest for the Atari 2600 is the one with the newest release date I've added to the list at the suggestion of AmyK, so I thought I'd take a look at it first. After playing it though, I'm convinced it doesn't fit my criteria. From the description, the game has 8 levels of increasing maze-like difficulty where you need to set a self-destruct mechanism and reach the exit before it blows.
Your character is given a light sword, which uses a small amount of energy and has a limited oxygen supply that acts as health, but both also drain slowly on their own. There doesn't seem to be much beyond this though, and it's lacking a fleshed out character (stats and skills), combat is basic (collide sword with enemy), and there's no other NPC, story, or quest interaction to be had. To classify it, it's an arcade style action game much like many other Atari 2600 games.
Many other of the older games aren't quite fitting either, so to save from flooding everyone with posts I'll start combining a few of the more alike games. Hopefully this won't be too confusing for anyone trying to follow along.
Sorry AmyK, I hope your other suggestions pan out a bit better.