I am particularly fond of puzzle games. I recommend you either do a text based GUI game, like Connect Four (http://en.wikipedia.org/wiki/Connect_Four), or Fifteen puzzle (http://en.wikipedia.org/wiki/15_puzzle).

If you feel bolder, you can try to do automatic puzzle solvers, like sodoku solver, or nonogram(http://en.wikipedia.org/wiki/Nonogram)

If you really feel bold, you can try to do a 15 puzzle solver, or a Connect four bot.

I can GUARANTEE you will learn a lot from this experience. Personally, I would try to do them in this order, from easy to hard:
Easy
- Connect Four Game
- 15 Puzzle Game
OK
- Sudoku Solver
Hard
- Nonogram Solver
Harder
- 15 Puzzle Solver
Hardest
- Connect 4 Bot

I have been writing a new sudoku solver every year for the past 6 years, and have been learning something every year form it.