Why not a game like tic-tac-toe? There are many aspects you could focus on to challenge yourself.
Algorithms: Make an unbeatable artificial intelligence. You can never lose Tic-Tac-Toe (only tie) if you play perfectly.
Graphics: You could also work on making a very flashy and pleasing graphical interface.
Realtime Events: Add a time limit for each player to make their turn. Making the game display a realtime countdown would add the element of event handling, which is important for making almost any game.
Modularity: You could challenge yourself to write good,
modular, code, by separating the game into distinct modules and writing OO code.
Gamplay / More Algorithms: You could try implementing more options:
- AI difficulty levels 0-9
- Play on a
grid. As opposed to a 
grid. Info Here.
- The above two items in conjunction would be extremely difficult if you wanted to really challenge yourself.
As you can see there's everything from novice-expert here. I am sure there are many more things you could do to turn tic-tac-toe into a challenging and fun programming problem. But that is just one suggestion; I would wait until hearing from others.