Loops

A very simple game that you could play with Xs and Os. It's certainly related to Go but has much simpler rules, and while definitely not as "deep", it can still produce some interesting competition.

The best board for beginners is probably 7x7x7, maybe 6x6x6.

The rules are explained here: http://www.scribd.com/doc/287823949/Loops

Here are a bunch of interesting variations: http://boardgamegeek.com/thread/1286815/variants

You can also change things up by playing with two moves per turn and/or the ability to place either side's color each move. The easiest way for beginners to account for pie while playing with two moves per turn is by playing only a single move on the very first turn.