Other suggestions:
-Tic Tac Toe/Connect Four (if you think tetris is too advanced...)
-Some sort of 2d real-time game (birds-eye-view or sidescroller for example)
-Other puzzle games like the "slide the mixed-up square tiles until you have the original picture" game
