I guess raw palette and image data is the fastest then. The palette would only be 64 bytes ready to be written to the color registers so encoding them like this only eats time and space, and the gain from RL-encoding the images is typically not very big.
If image size does matter then plain sliding window compression might be better. It's very fast to decompress and compression ratio is always better than RLE. Ask Photon for his compressor, it does just this.