How to search for an optimal dithering pattern?
I think you're on the right track. If you can produce an objective scoring algorithm for the output which more closely resembles your subjective perception than 1:1 error you could definitely use simulated annealing to derive from that an optimal matrix at a given size N.

Your current scoring calculation for error seems to focus too much on high-frequency information (details), and not enough on low frequency information (larger areas) - notice the results you deem subjectively superior, if blurred (low-pass-filter) more closely resemble the input image (if also blurred) compared to the results you have deemed inferior.

If it were me, my next step might be to try something hierarchical in order to avoid bias toward any given frequencies, maybe a quadtree where at each level 1x1, 2x2, 4x4, etc. I average the values of the node's children, then scoring uses the error between trees.