Why would you bother with with indexed textures when we already have DXTn, BC7 and (in the future hopefully) ASTC? These formats will give you better image quality and better compression ratios.

For 2D images with a low shade count palettes can easily look better than those compression methods (though this heavily depends on the case). Also there's the issue because of the silhouettes: the compression formats that support translucency either do it by increasing the size or by reducing color precision even more.

The problem with the look-up idea is that it breaks texture filtering... This means you have to do it manually by reading the texture multiple times instead of just reading once, because otherwise you'll end up blending the indices. I think this is probably my biggest put off for attempting to use this idea (even if in practice it may not be as bad as I'm making it out to be, since usually you wouldn't be doing some of the really expensive operations 3D games do).

In practice I imagine this is one of those "try and see what happens" situations.

 

Why would you bother with with indexed textures when we already have DXTn, BC7 and (in the future hopefully) ASTC? These formats will give you better image quality and better compression ratios.

 
And worse palette animation.

Performance concerns are silly (if one has so little memory and so many textures that degrading them to 8-bit colour is acceptable, using high-performance compressed formats is also acceptable), but the indirection of using a palette allows an enormous variety of tricks with carefully drawn pixel art (for which mipmapping and interpolation are a very bad idea).

You do bring up an interesting point in that it's not entirely clear what the OP is trying to achieve with these textures. He only talks about performance and memory concerns, so I'm not sure what he's talking about in his last paragraph.

That said, I think palette-swap animation is probably not what anyone wants. It's certainly cool in 8/16 bit games with "extreme" (by today's standards) memory and rendering limitations as well as other idiosyncrasies, but it's not clear that there's any incentive to do it today.

To be honest the only time I've ever seen palette-swap animation combined with OpenGL is in that 3D Maze screensaver for Windows 95, on those weird animated fractally textures you could choose in the settings, and even then I'm only guessing that's what was going on.

For 2D images with a low shade count palettes can easily look better than those compression methods (though this heavily depends on the case). Also there's the issue because of the silhouettes: the compression formats that support translucency either do it by increasing the size or by reducing color precision even more.

The problem with the look-up idea is that it breaks texture filtering... This means you have to do it manually by reading the texture multiple times instead of just reading once, because otherwise you'll end up blending the indices. I think this is probably my biggest put off for attempting to use this idea (even if in practice it may not be as bad as I'm making it out to be, since usually you wouldn't be doing some of the really expensive operations 3D games do).

In practice I imagine this is one of those "try and see what happens" situations.

Depending on the OP's requirements, might it be worth storing the textures in a paletted format (even like PNG?) and then sending them to the GPU as RGB data? It seems very likely that you'd not get much benefit from trying to process the indexed data in real-time on the GPU, but if you're mainly trying to reduce the storage requirements of the game (which seems likely if the OP is using OpenGL ES) then this seems like it might have some value (and require relatively minimal effort to implement)

It wouldn't be faster because it requires a dependent texture read. You mentioned GL ES so here's Apple's advice (source: http://developer.apple.com/library/ios/#documentation/3DDrawing/Conceptual/OpenGLES_ProgrammingGuide/BestPracticesforShaders/BestPracticesforShaders.html#//apple_ref/doc/uid/TP40008793-CH7-SW3):

Dynamic texture lookups, also known as dependent texture reads, occur when a fragment shader computes texture coordinates rather than using the unmodified texture coordinates passed into the shader. Although the shader language supports this, dependent texture reads can delay loading of texel data, reducing performance. When a shader has no dependent texture reads, the graphics hardware may prefetch texel data before the shader executes, hiding some of the latency of accessing memory.

Memory savings are moot - are you really that short on video memory anyway? Maybe on mobile devices (I note that you mentioned GL ES) but there are other strategies to reduce video memory usage - compression or just flat-out reducing your texture sizes (who needs a 1024x1024 texture for a mobile device? Maybe in a few years time - by which time one may expect that video memory sizes will have increased too - but not today).

Texture upload performance could go either way. A standard texture change doesn't upload new data from GPU to CPU; it should be all resident on the GPU to begin with (for devices with shared/unified memory it won't matter one bit). For dynamic texture uploads, the required synchronization is going to kill you far more than the amount of data used.

On today's hardware texture reads are expensive operations - that's why you want to keep them to a minimum. And one's natural inclination to save memory must be kept in check because doing so can often be at the expense of performance, and often in quite unintuitive ways - the rules that you'd apply to CPUs just don't always work well on GPUs.