Last night I discovered Blokus.
Blokus is simple to understand, but very hard to master. I’ve actually only played a few games but immediately found the official version for Palm so I could play while on the go. There are online versions as well as board game versions. Boing Boing described it as a cross between Tetris and Go and that gives you a picture at least of what it’s like, though until you actually play, you won’t fully understand.