Some of the asymmetry might be regained if anubis had thousands of variations of PoW algorithms, each different enough that they must be solved independently.

I wonder if AI might be able to come up with new PoW algorithms in a nightly CI job so every day is a different puzzle...

You can do this on yours. Just have the client and server add an extra "2" after the challenge key or something. A different client which extracts the challenge key and does its own processing will only generate invalid responses.

...That sounds like entropy? As in, the thing computers are bad at (truly random numbers) and /dev/urandom in your kernel already spits out an approximation of?