Have a look at: http://produkkt.abraxas-medien.de/kkrieger
This group used procedural synthesis to build a working FPS in < 96 kilobytes. Repeat, 96 kilobytes. They've also got graphical demos weighing in at about 64KB. I'd like to know how it's done!
They gave presentations about it at Assembly '04. However, I am unable to the videos anymore. It is mentioned on their website for all that is worth though.
http://produkkt.abraxas-medien.de/