These are so tiny because they generate the texture data mathematically (procedural textures), as well as do some amazing compression on the code and data. I remember reading about the demo scene once especially with .produkt - they were given approximately 72 hours to compete a demo, competely with 3d graphics and sound, using no external 3D API's, with code and data all together under 100K. They barely made it, and they were doing some amazing things like writing their own audio trackers and such using assembler in 100 bytes or so.
The procedural textures are huge when generated, 512x512 and more. Like I said, they're all mathematically generated, which is how they make the final product so small. Goes to show you that a lot can be done using math. However, not everything always looks good.