Soldam immediately comes to mind as the deepest cut I can think of. You might not be too impressed the first time you put a quarter in, the singleplayer modes are nothing too special. But if you can get a second player, it has one of the most interesting versus modes I've seen in a puzzle game. Sadly, you do need a second player, there is no versus CPU.
This game got a modernized remake on Switch a while back, they added online play... but they still didn't add CPUs.