That won't cause implementations to be fixed. The implementations in question are in devices that are old (DNS is over 40 years old) and will never be upgraded. Affected users will just choose a different DNS resolver. Pretty soon word will get around that "if you don't want a broken device, don't use CloudFlare for DNS". It's less hassle for CloudFlare to just maintain the existing de-facto standard.

Is the property of an answer being ordered in the order that resolutions were performed to construct it /that/ fragile?

Randomization within the final answer RRSet is fine (and maybe even preferred in a lot of cases)

That would be a Flag Day initiative. ;-)

Honestly, it shouldn't matter. Anybody who's using a stub resolver where this matters, where /anything/ matters really, should be running their own local caching / recursing resolver. These oftentimes have options for e.g. ordering things for various reasons.