Previous games that my students did that seemed to make good projects

• Battleship
• Boggle (checking if words are correct and AI is pretty hard, though)
• Chinese Checkers
• Clue (this was really complex)
• Connect Four
• Dots and Boxes
• Gin
• Go Fish
• Mancala
• Mastermind
• Othello
• Scrabble
• Set
• Parcheesi
• Wordsters
• Yacht / Yahtzee
• 3D Tic-Tac-Toe

Frequent misdirections (projects my students really seem to want to try that don't work out so well)

• Poker: the AI is really hard.
• Blackjack: the AI on this is really dull; you just implement a set of rules you can look up anywhere. I'd rather you do something that you need to think harder about.
• Bowling / Football / other sports simulations: These usually turn out really bizarre.
• Some kind of adventure / role playing game: this nearly always devolves into a massive set of nested if statements that don't really give you the opportunity to think about more interesting algorithms. This can be done right, but it's easy to miss the mark.
• Risk: getting the map is pretty hard.