Proof of work for standard computers
$\quad$ chosen-prefix partial collisions for scrypt

This does somewhat better at #3 than your second option because

working requires storing previously obtained scrypt outputs.

(I think it would be better to require a at most a given Hamming distance between the outputs rather

than equality of a specific set of bits of the output. $\:$ The first of those would require storing the

entirety of the outputs, while the second would only require storing the relevant bits of the output.)