Bit-Tech just published pretty interesting article/interview called Procedural Texturing: Gaming's Future. The interview covers the use of modern mathematical techniques to create textures instead of the standard use of compressed image files. Pretty interesting reading.

At least 70% of the textures of your game could be replaced by procedural equivalents. 70% is a minimum number of textures you can replace, in actuality the likelihood is you can replace more. So for example: replace 80% of the textures and if those textures occupy 50% of your game size, the overall game size would end up a little less than 50% smaller.

I have some actual examples from a recent game,
Roboblitz. In this game, we replaced about 95% of the textures. The game has 6 levels and for each level the developers would use 80MB of compressed textures. So, let's do the numbers, a total of 6x80=480MB. Using our tools we replaced the 480MB with about 3MB of procedural data, a pretty spectacular decrease in game size.

The game now fits within 50MB and can be downloaded through Xbox Live. Without our technology this game would weigh approx 50MB-3MB+480MB=527MB. So the gain, for Roboblitz, we saved 90% of the entire game size. That is a massive gain for the developers which allows them to reach the Live audience - something they couldn't otherwise have done.