I don't see any reason you can't parallelize transaction processing, which seems to be the majority of the work miners are doing.
Alice has $10, Bob has $0.
Block contains "Alice pays Bob $5" and "Bob pays Alice $5".
One node will accept this block, another node will reject it because thread scheduler will change the order of transaction processing.
More interesting effects will happen during order matching if you have something like Asset Exchange.
Not every transaction depends on the transaction before it. You can parallelize 99.9% of transaction processing and keep 0.01% serial [if one transaction depends on the one before it in the same block].