It's not a bad thought, though there are a number of challenges. One thing PoW has going for it is that the difficulty of computation is well known and easy to adjust.

Specifically for the codec cases, it's not that we can't come up with better codecs, but that they require more computational resources to encode and even decode. We have ones now that are still a bit much for mainstream and using bandwidth/storage is a better market fit. As for the 'overall quality' this is subjective. Anything objectively defined is optimizing for something humans may not appreciate.

So what we're talking about is generalizing the hard to compute, easy to verify of finding hashes to other computations that are useful to some parties--a computational market. I do rather like this, like kickstarter for computation. A problem gets posted, with a verifier. People can choose which ones they want to sponsor and how much. Solvers can choose which problems to solve.

Even thinking this through, I think it's still useful to have a PoW hash-based blockchain just to record the first solutions. So we're back to being limited in the number of solutions we can record per second.