Funny how the very same contacts lost pictures on two different phones. So there must be something specific causing it, it doesn’t seem to be random.
I’m so happy that I had a recent backup. Just deleting all contacts and restoring them from vcf was the quickest way to get everything back.
P.S. There is also a GOOD NEWS: the browser fix has made its way to this update so that it no longer always starts with that search page or whatever it was.