JPEG compression is very impressive considering the complexity of that format. Other formats we could try are PNG but I'm unfamiliar with how long it takes to decompress compared to JPEG. One format worth trying is DXTC http://en.wikipedia.org/wiki/S3_Texture_Compression which is the standard format for DirectX textures. It will compress a bmp image into a little less than half the size it is normally and can be drawn very quickly. Because the images are being played back in video format there are a lot of size optimizations that can be done on the DXTC format such as keeping some or all of the palette data for the next frame. For just standard DXT1 compression I've been writing a super fast asm routine to decompress the images and I think I have an idea for a video based version of DXT, both of which I'll post once I finalize them.

The color depth could also be reduced, from 16 to 8 bit.

That's a possibility but I think that should be done on a frame by frame or segment of frames basis. As in there shouldn't be a single palette for the entire video but instead each frame or segment of frames should define a new one. You could even go as far to define an 8 bit palette for each frame then use 8 bit DXT1 compression for that frame. I'm also thinking it would be a good idea to interlace the video to increase speed while cutting size in half. 

Hello,
this is another version of the player. It uses 96x50 frames (4 bit colors), uncompressed. Video has 12.5 frames per second (the calculator was able to keep sync with computer, where the original video was playing)
The maximum speed (before I implemented timing) was 15.88 frames per seconds.

Is the rar file supposed to be able to sent to the calculator as a rar, or should only the raw file be sent?

Please, extract the rar and put the raw file in the calculator. I rared it to save bandwidth (and I would probably also touch the 7MB limit set on this server)

The frame rate looks great! Is the video supposed to be in grayscale, or is this something that was added for compression?

Both:-) The video is in gray-scale (16 colors) to reduce video size.

Maybe RLE could be used for compression? It's popular on older calculators since they only have 2/4 colors. Using RLE with 16-bit color won't really work, but maybe it's good enough for 4-bit?

Yes, I will probably try RLE as a next step.

Indeed, the frame rate looks very good, WAY better than in Z80 Calculators and the Nspire, but that's because of the colours and the better processor. nice job MPoupe!