An off-the-wall suggestion that may be redundant with newer ver.2 pixel shaders/fragment programs, but i’ll suggest it anyway:
Instead of binding a texture in a normal way, allow a ‘texture program’ which allows custom code to be used instead of a texture lookup. Basically a user program that, given a texture u/v coord will generate a texture colour. Performed on the hardware so taking up much less memory, faster upload speeds and more varience in surface detail. Obvious uses would be perlin noise based texture equations.
Current hardware is not generally capable of this kind of thing.
ATI_fragment_shader/NV_register_combiners expose what can be done now on consumer cards, with 3DLabs’ Wildcat VP already going a few steps further.
ARB_fragment_program, OpenGL2 and GL2 extensions will expose that sort of functionality in a uniform way, if the hardware is capable of doint it.
So the effort is already on the way 
Actually, you don’t need a specific “texture program”; current ARB/NV fragment program can do the job of user-defined texture generation. After all, the fundamental idea of a texture is “a function that takes 1-4 inputs that produces a color output.” Whether that function is explicitly a “tex A” call that calls a program or a sequence of fragment program opcodes is irrelevant; the result is still the same.