I've been toying with the concept of very simple, distilled strategy games that don't take long to play, but involve some brainwork on some level. I was already thinking about putting a game of some sort on a very small (maybe 5x5) board, and then I stumbled across a description of Quadpawn, an old C-64 game. Each side has four pawns on a 4x4 board, and the objective is to either get a piece to the other side of the board, or prevent the other player from being able to move. The game concept is also described on algorithmist.com.
Anyway, here's a version in Flash. The source code is available on github as well.
Update: If you find this interesting, please checkout Five Pawns, which is the same game but played on a 5x5 board.
The game is simple, and once you get the hang of it, it's not hard to win most of the time, but it stayed enjoyable the whole time I was playing it.
The sourcecode is pure AS3, so you don't need Flash to compile it. Among other things, it has a pretty clean implementation of the minimax algorithm, something that is reasonably hard to come across.