In simplest terms, I feel that these texture compression schemes should be available on all android devices, but I'm not sure about 2, and even then, I'm not so sure about 1.
- compressed paletted texture
- ETC1 (RGB 8 bit)
I can't seem to find the docs on this at developer.android.com. :(
If anyone just knows this info off the top of their head, I bet they'd be here at StackOverflow. :)