I don't see how verifiable CPU-only mining solves the processing power advantage in mining. Pools, farms, and botnets can still be used get an advantage.
Botnets can be muted significantly by requiring 16GB of memory. One tradeoff is that makes mining not instantly accessible to users who don't have that much memory installed.
Another strategy is to require say 4GB memory and hope this causes those whose computers are in a botnet to notice their computer is running slow and paging virtual memory to disk.
Botnets become less of a problem as the number of legitimate cpu miners increases, because the botnets are being sourced from the same supply of total PCs in the world. Eventually legitimate cpu miners will far outweigh the botnets, so can gradually relax the memory requirements to fit the average PC.
I wrote in the OP that pool sizes must be limited. I am not going to tell you now the secret way to do it.
Don't you need to enforce a "one connection per person please" policy somehow? If there's a mathematically rigorous way to do this of course that's the way to go.
I was thinking that the network might require a user to solve a capcha to connect and timing out the connection after a few hours (probably already has been proposed). I know, this is terrible idea but it might be effective at keeping the mining egalitarian, which I think is what you are aiming at.
Impaler and I discussed that. I decided it is untenable basically because it requires top-down control in order to generate and verify the captchas.