My personal favorites are (board)games which create complexity from simple rules, for example chess, go or FPSs in the virtual world. A boardgame which comes close to this ideal is Carcassonne. The rules can be explained in less than two minutes and it is great fun! See below the recording of a nine hour game:

Don’t be afraid though, that one was played using tiles from 3 sets. A normal game lasts around 30 minutes. You can buy the game on Amazon (disclosure: the link contains my affiliate ID) or, if you are in Romania, you should check out cutia.ro.

Have fun!

PS. There seemed to have been a site where you could play it online, but it seems to be offline. There is some speculation that this is due to copyright violation on the part of the site and/or due to the site being hacked.