The Interactive Way to Go: http://playgo.to/iwtg/en/
Its also available in 32 other languages: http://playgo.to/iwtg/
Beyond that I recommend 9x9 games, on Windows download yourself a free copy of iGoWin: http://www.smart-games.com/igowin.html or on OSX or Linux check out GnuGo.
There's also a Linux live cd/distro with lots of learning tools by the name of Hikarunix: http://senseis.xmp.net/?Hikarunix
Computers are awfully predictable and have a hard time even on a 9 by 9 board.
Next up, I would look at checking out a local Go club, maybe read a book or two, maybe check out igs/kgs.
Move to a 13x13 when you want the game to get more complex. Raise the handicap again when you do so.