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 lead to the opposite order of transactions.
Good point. One fix is to allow account balances to dip into negative, keeping track of which accounts currently have negative balances. And when finished processing, accept the block only if no such account balances exist.
Again, two steps, each of which can be done in parallel.. or maybe the second step can even just be, "Is list empty?"