Referring mainly to games from the 80s only here, especially early 80s:
Most 80s arcade games are simple and repetitive: Asteroids. Space Invaders. Pac Man. You get past one level and the next one is mostly the same just faster. Other games had a few basic levels, but even an intermediate player could get past them all and then you just went back to where you started, only with higher difficulty.
But some of them had surprising depth. Interesting level design, introducing new types of obstacles ,or gameplay mechanics that were way ahead of their time.
Such as Wizard of Wor, probably the earliest game where two people could play simultaneously. You even had the choice of playing cooperatively or try to kill each other. And the mazes were all different.
Or Punchout, with a decent number of opponents which got pretty brutal after the second one who all had their own fighting styles.
Amidar, a surprising little nugget from 1981 I believe, where you play a guerilla trying to paint a board, kinda like in Pacman, but the colors and structure of the maze kept changing.
Qbert, a game with tons of personality and a wide variety of enemies.
Crystal Castles, great level design and an extremely unique control scheme(track ball where you could control your bear’s speed as well as his direction in very subtle ways).
Gotta mention Dragons Lair/Space Ace/Cliffhanger too. Just incredible ideas and it’s a shame that type of game never really advanced. I hear it was because of the huge cost of production and the unreliability of the laser discs, but in 1984 or so these were just amazing pieces of technology.
Any other great old gems that you love to play that go beyond the simple, “kill all the enemies, next board same as the last but faster” template?