I should clarify that rules 4 and 5 (as described above) do require a total ordering by block. It’s just that validating scripts (input->output) does not, that’s a partial ordering (3). And the forward reference (1) and internal double spend (2) checks impose no ordering requirement.
The trick to obtaining maximal concurrency is factoring necessary constraints such that no unnecessary order is imposed.
Existence and spentness are all about block order, we call that “confirmability” and perform these checks in a “confirmation” phase. Checks such as script execution, and the related prevout queries, run concurrently across blocks in the “validation” phase. Anything that is block-context free (header context is always available) is performed in the “download” phase. The three phases run concurrently.