While the first can be easily done in parallel, the second type needs a more contextualized solution. Could you elaborate on the procedure?
I think we should handle it in a similar way as in transaction verification. Having some chain of blocks A->B->C->D we can verify block D in one thread and block C in another thread. We can verify multiple blocks in parallel and as long as everything is ok, we would get a speedup. But: it is possible that block A is invalid, and then we should reject blocks B, C and D later. But assuming that bandwidth is not a bottleneck, we could for example allow downloading some data without checking everything and reject that later if needed. For example, if we have 4 threads, we could verify each four blocks separately and later join results from them. Having full context is not needed. For example: if we want to verify block D without checking previous blocks, we can assume that our transaction inputs are correct. We store that assumptions somewhere. Later, when block C verification ends, we can collect all UTXO's created in block C and match them with assumptions we made for block D. Of course it is possible that not all assumptions will be cleared, but after clearing all assumptions for some block, we could safely say that this block is valid. And if finally we would have all assumptions for all blocks cleared, then we would have everything validated. More than that: if there would be some long, but invalid chain, we could create SPV proofs for other nodes and share them, speeding up stale chains rejection even further. But to start with, block verification should be optimized.