Tic-Tac-Toe is a pretty traditional game to use as an intro to minimax. You can get more complicated by making it bigger than 3x3 or even 3-dimensional.

After that, you can move on to checkers (or...