I second Tetris (array management, conditions, functional game mode states).
I also recommend Mastermind (array management, solver algorithms, parsing), Frogger (timing events, keyboard input), Noughts and Crosses (artificial intelligence), Matching Pairs (game modes, random sorting), Slot Machines and Arkanoid (physics).
Best bit of it is that all the above (bar arkanoid) can be coded to output as text only, meaning you only need to display everything either in a textfield with a fixed width font, or in the output window.
Keeping graphics seperate to programming encourages a specific mindset that covers problems from a purely coding side of things, and doesn't slow you down when it comes to taking your code and assigning graphics to it (which in turn, promotes an OOP way of thinking later in your programming career)