Fun fact: if you wanted, you could make even more compact games on a modern computer using procedural generation to cut down on resources. (way too heavy and ram consuming for old consoles)
If one want to see what you can do with limited executable size on a modern computer, I suggest googling for "4k demo", and prepare to be amazed
(thats 4096 bytes, including all code and resources)
Those guys even compress/generate their code...
The 4k demo guys' main compression was in size. I'm not sure if that's what you were implying - but the 4k demo is very cpu heavy and would not run on any older consoles - I had trouble running one of those demos a few years back. There's always some sort of minimum tradeoff with any sort of optimization.
Though there is Elite- the video game "which was originally planned to contain a total of 248 (approximately 282 trillion) galaxies with 256 solar systems each. The publisher, however, was afraid that such a gigantic universe would cause disbelief in players, and eight of these galaxies were chosen for the final version".
Pretty impressive for a 1984 game..
Edit: For its sort of modern successor (at least based on large universe), there's Infinity: The Quest for Earth, which is also planned to have a fully procedurally generated, actual-sized galaxy (where you can fly down to planet level).