Tons of problems are easier to verify than to solve.

do any of them involve mining bitcoin?

sure

Maybe there is a way for the server to ask the client to do the work?

Something similar to proof-of-work but on a much smaller scale than Bitcoin.

just add some delay to your response, we don't have to waste any more energy on meaningless calculation.

Adding delay means you have to keep more connections open at a single time. Parallelism doesn't favor a server if your problem is already a small server getting hit by a big scraper

How expensive is it to just keep a connection open?

About 20 kilobytes of socket + TLS state, if you've really optimised it down to the minimum. Most server software isn't that lean, of course, so pick a framework designed for running a million or so concurrent connections on a single server (i.e. something like Nginx)

Right it would need an algorithm with widely different encryption speeds vs decryption speeds. Lattice-based cryptography maybe?

Hash functions are all you need.

Yeah, searching for hashes with some prefix is easy to set up.