Pick something useful that has low monetary value on the open market, like number theory problems or protein folding or something.

I could imagine the RandomX code execution approach being re-worked to incorporate useful scientific computation, and this being worked into the currency itself. It might be possible for people to stake money on compute units and then have the money go to the miner who solves a block in proportion to compute units performed. You'd have to put a lot of work into making this non-gameable though.

Maybe something can be done here with homomorphic encryption too, so the miners would not even know what they are computing.

A lot of interesting open cryptography and math work here.