I kind of wish they start sending records in randomized order to take out all the broken implementations that depend on such a fragile property

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.

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.

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)