What games best represent well-known computer science problems?
If by 'show computational theories in them' you mean correspond to complexity classes or fit nicely within complexity classes, then you first have to generalize the game to depend on some parameter $n$. For instance, for a game of Chess with a clock (and maybe a 50-move no checkmate rule) on an 8-by-8 board there are only a finite number of possible games. Thus, everything about the game is solvable in $O(1)$.

To overcome this, complexity theorists usually define a generalized game. So for instance a variant of chess on $n$-by-$n$ boards, then standard complexity questions can be asked. In that case, a lot of the 'fun' two player games become PSPACE-complete or EXPTIME-complete. For instance Reversi and Hex are PSPACE-complete and Chess, Go, and Chinese Checkers are EXPTIME-complete. You can learn more on wikipedia

In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called phutball deciding if a player has a win in one move is NP-complete. Solving who will win the game in general is PSPACE-hard given arbitrary initial configuration