Castle Wolfenstein on Atari 800. A long game with fixed amount of ammunition, ability to use disguises, ability to search bodies, and a distinct ending.
It just blew me away. I played through it 4 or 5 times.
I loved Adventure on the VCS too. In those times, anything with an ending appealed to me. The fact that Wolfenstein had an ending and took days to complete was just amazing for me at that time.