This is a very important question and trying to answer this I am understanding the mechanism I want to design much better. Thank you for asking it!

The PoW system currently used in Bitcoin has the same problem. It solves this problem by offering an extremly large search space and a situation (hashing) where nothing can be said efficiently or systematically on how to find a good solution. Thus, the solution method is random parallelization of a brute force search. This solution method introduces a random element into the situation (which was not there from the beginning: the PoW task is not random).

So, parallelization introduces a random element here. If we now prevent parallelization completely and produce a PoW system which makes the solver work through a sequential number of deterministic steps, the fastest single core processing unit will win every block.

Thus, we must reintroduce a random element in the PoW. Possibly, there are two construction elements for building a PoW: Two tasks could be chained one-after-the-other (leading to non-parallelizable work) or combined (leading to parallelizable work). Currently Bitcoin uses only ONE of these construction elements. Using ONLY the other one is a clear fail (as FreeTrade just pointed out). Using BOTH mechanisms could lead to a new, different PoW.

The question is: Would there be advantages when using a different PoW?

In addition to the ones outlined in my above posts, I see one more: Currently the time for solving a PoW is distributed according to a Poisson distribution (Satoshi describes the consequences of this in his paper). We have a parameter (difficulty) where we can tune the mean of this distribution, but we cannot independently tune the variance of the distribution (with Poisson it will always be equal to the mean). With a different PoW system we will be able to obtain different distribution shapes (possibly with a smaller variance than Poisson). This could make the entire system more stable. Certainly it will impact the Bitcoin convergence behaviour. For the end user the impact might be a higher trust in a block with smaller waiting times.