I disagree: The default should be deterministic but slow, and one should have to go out of their way to e.g. parallelize stuff, at least just enough to understand the risk of it becoming non-deterministic if done wrong.
Backwards compatibility is one of the most important things to do to keep people using your product - if I have to debug and change my code to use version 2 of your product, it's not much more work to switch to a competitor. It's also incredibly difficult to deliver backwards compatibility and requires intentional planning in advance.
That all but ensures nobody will care then. Performance is, sadly, not a big motivator in most projects.
Both could be satisfied with a single-threaded make keeps the standard order to ensure backwards compatibility, but `make -j` that also turns on --shuffle. Which is also backwards compatible, because timing of each target might rearrange them.