> Making the proof of work do “useful” things would lower the cost of said work thus lowering the barrier of entry to an attack.
How does this follow? If the work is so universally useful that it lowers the cost of the work, it lowers the cost for everyone. Not just "attackers", but "defenders" as well.
As it happens, Bitcoin miners mine not out of the goodness of their hearts but for financial profit. Bitcoin POW is "useful" to them: It gives them more money than they put in. They do it precisely because the cost of said work is lower than the returns.
The problem is that the usefulness of said work might not be the same to everyone. Let's imagine a potential coin where mining involves cracking hashes.
This work is useless to you and me (thus the only extracted value would be the reward from mining), but might be useful to someone who's got hashes to crack (so they get extra value out of the same process). In this case, the latter party can enjoy a 51% attack at a fraction of the cost of the former.
In fact, nobody seems to have read the first page, which has a note that the definition of "proof of useful work" in that paper is trivial. An updated version is available here:
Making the proof of work do “useful” things would lower the cost of said work thus lowering the barrier of entry to an attack.