It's pretty amazing what people can do, using such little space. Oftentimes, a full-sized game is emulated, and shrunk down to 4kb. An example of this is Left 4k Dead. It's pretty fun, but really hard. I can't speak for how true it is to Left 4 Dead, since I haven't yet had the pleasure of playing it.
The winner from 2008 is a game called Spiderball4k, and your goal is to get the ball into the circle. You control your 'arms' which you shoot out like Spiderman shoots out his webs. If you touch any walls or objects you die. Difficult, but fun.
Fkconflict is a fun version of Risk. Instead of choosing which countries to attack and move from, they are randomly selected. During a round, a random country is selected, and you can choose to attack from that country, move from that country or pass. Another random country is selected, and this continues until all countries have been selected. A pretty fun take on the game.
Another one that's not really worth a screen is Scr4mble. It's fun, mostly cause I love word games. It's a great example of how 4k or 4 is often cleverly inserted into the title. Left 4k Dead is one of the best in that regard.
Passage isn't a 4k game, but it's graphics/simplicity remind me of it. It is an artsy game which lasts 5 minutes. Before you read any further, I suggest you go play it, since it's impossible to discuss without spoilers.
Last warning before I start talking about it... I didn't get at first, which is to be expected, since it's on the weird/artsy side, but I liked it by the end of it. Given that the end is only 5 minutes away, it doesn't take long to warm up to. Your first choice, marriage or not? You get more points by being married, but that damned woman holds you back.
If you avoid marriage, and live the single life, you get less points, but you have more manuevarbility. You can go around hunting treasure in a maze, and don't have to worry about finding openings that you can both fit in. (Not meant to sound dirty...)
It got pretty big coverage, here's a few articles on it. I played through it twice, and don't feel like I've learned anything, (since I already knew to avoid women) but I feel a tear in my eye... (But not really, I'm too manly for that.)