If Big-O lets you run every possible algorithm in "parallel" while still being in some sense "optimal," that seems like yet another exploit?

As I read it, that was sort of their point: if the theorists were blindly focused on Big O complexity, they could 'cheat' by invoking the universal search algorithm as a good-enough solution to a huge class of problems; but they don't, because they're not mindlessly playing a game where Big O complexity is all that matters.