Another pass.
We're looking for a substring with the largest number of unique values. If we have unique values, we can paint each value with a colour close enough to the expected value that humans will see them as the same.
Maybe?
Yes, it helps to have more unique values. We want each repeated byte to occur in part of the pattern where a color also repeats.
What I do is search for substrings with the fewest repeated bytes that don't match the target pattern. I prioritize first minimizing conflicts between light (white and tan) vs. dark (black and red). Reducing other conflicts is a tie-breaker.
The featured gif has 79 "mismatched" pixels out of 494, by the black/white metric. I've found candidates with as few as 75, but subjectively I didn't think they looked as good.
I can sort of think of:
1) Collapse the colours in the palette to the minimum necessary to be seen as "Waldo". The more slack in the gif palette the better - 24bit colour vs 16 colours (or fewer) in the starting image?
2) For each substring in Pi, map the hex value to a colour (or close to the colour) to match the expected image.
3) find best match - how?
How to backtrack though?
Perhaps pin important fragments?
The glasses and chin seem more important?