Multithreaded playback

(BTW, I have found that turning off GMC and B-Frames during encoding benefits decoding speed, at the cost of somewhat increased file size. But it is damn well worth it if you want to watch stuff on low processing power devices.)

As to your comment about needing large amount of memory for the cache:

You could stop decoding just before the RLE codes are unpacked, and do that decoding step then just right before the frame is displayed. Unpacking the RLE and applying the delta-frame should be pretty straightforward.