It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet).
Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I have yet another different vertical locality suggestion to try:
While encoding/decoding keep a ring buffer the size of one full line of the image, storing each encoded/decoded bit there. Then add a variation of method #3 (The difference to the previous pixel) which instead encodes the difference to the pixel above the current (the last pixel from the ring buffer). Maybe, due to the limited "tag" space it would not be worth it to implement it for DIFF8, but only for DIFF16 (taking one bit from red to the additional tag bit) and DIFF24 (I'm not sure which bit I would steal there).
Edit: Also, when thinking about video encoding in the future you may want to keep a ring buffer fitting the full last frame of video. And then temporal locality is probably even more important, so then you may want to change the tags to encode more commands relating to the pixel from the previous frame.