I think Minesweeper is a great tutorial game. It forces you to learn different variable types, data structures, loops and user input at a minimum, and it's really easy to expand on to make it more complex without requiring unique or difficult logic. Turning it into Battleship is a fun progression - I hadn't considered that, but I like it!