You can also buy Goban from the app store to play GnuGo or Pachi (both bundled), but it is a bit buggy (and not really better than the older free version). They do respond to bug reports though so it sounds like they are actively working on it.
Start out playing 9x9 against GnuGo. Give yourself a 9-stone handicap, you should probably win. Take away handicap stones until you can win with a 3 stone handicap.
In general you don't want to play an AI at less than 3-stone handicap or you will learn bad habits.
At that point, play against GnuGo 19x19 with a 9-stone handicap. If you are a beginner around 20kyu, you will find it a challenge to win.
I've been practicing consistently for the past couple of months. I do problems on goproblems.com or from a few iPhone apps. I've played a couple of games against ranked bots on kgs and am ranked 15kyu there since I beat a popular 16kyu-ranked bot. KGS is inflated through so I'm probably around 20kyu, still a complete beginner. I beat GnuGo 19x19 at a 9-stone handicap but not quite yet at an 8-stone handicap.
Once you are able to beat GnuGo 19x19 at a lower handicap then you can start playing against Fuego or Pachi. But at that point you should also already be playing humans regularly - it's a very different playing style in that you'll come across clearly bad moves that you will have to learn to recognize and take advantage of.
I don't have much time now to play, but was around 4-5k in KGS and like me, there are always a bunch of folks ready to play with you while explaining the rules/strategy.
Regarding clients, there are a few options. CGoban2 is the only client you can use to access KGS, which is currently the biggest English-speaking server. You can also try online-go.com which is entirely browser-based so you don't need a client, and there's also IGS, a Japanese server which can be accessed through their own client called GoPanda2 or other clients like qGo2. There are also two servers called Tygem and WBaduk which are mostly Korean. They have proprietary clients you can run through Wine. I think they're supposed to be accessible through qGo2 as well, but I haven't been able to play through it, only observe others' games.
Also, if you're just learning, http://senseis.xmp.net/ is a great resource.
If the Mac version of SmartGO has features similar to the Windows version, it should be excellent. But, they've been focused on iPhone/iPad apps so it hasn't come out yet.
Playing against computers will teach you bad habits and will not be helpful past the very basics. If you want to do exercises, try e.g. Tsumego (for Android at least).
And the best way to get started is to find your local Go club, take a friend with similar level to you (ie. complete novice) and join their game night (my local go clubs meet in bars). Ask a more experienced player to over-the-shoulder for a few games. This is how I got started.
KGS: Kiseido Go Server IGS: Internet Go Server OGS: Online Go Server