Like the sibling comments have indicated, many apparently sequential computations are actually parallelizable. I'll just add finite automata as another example in this category. On the surface it looks quite sequential (process one input at a time), but there are nice parallel algorithms that you can even implement on a GPU!

So yeah, there's a lot of nonobvious parallelism in the world. Just because something seems sequential doesn't mean it is.

I think the real reason why a lot of software is sequential/inefficient in practice is because we're just not smart enough to figure out how to optimize it (or don't have the proper incentives/it's not a priority). But that's something that's conceivably solvable; it's not limited by laws of physics the way hardware is.