This is when I lament the loss of palletized textures as a standard. All of these images would hold up quite well as an 8-bit texture. Sure the palette take up 768 bytes, but that's usually fine. You can do this with a LUT in a 1x256 pixel texture on modern hardware I suppose.
On the right is the 8 bit version of the same image.
EDIT: BTW, I realize that a 4 bit DXT image is half of 8 bits, and that you're probably packing additional data in the other channels...