What games to create first?

Try: Hangman or X's and O's. If those are too easy, then try Tetris, Brick Breaker, or Space Invaders. You can really do a lot with just the console.

I believe sudoku is a really cool challenge to implement, using the console only.

Well you can try a text based RPG (basics atleast) and then build onto it with new stuff you want to try out.

If you're using XNA with c#, look at pong, breakout and blackjack. All are good beginner projects with scope

I like card games. They have a clearly defined set of rules and a very rudimentary intro to graphics. Trying to program AI to play the correct card in each situation is a good intro to a lot of logic.

Pacman and maybe a marble madness type of game? That would involve a physics type of library i believe though.