I remember thinking about nonlinear reward factors, they have some interesting properties:
linear: reward derivative is constant per added effort (irrespective of identity)
nonlinear: small efforts can be rewarded (say reward=sqrt(effort)) more than big efforts or vice versa (reward=effort^2)
I will henceforth refer to Reward as R and Effort as E
However keep in mind that bitcoin is pseudonymous. Keep in mind also that there is a difference between verifying a user is human (say captcha) and verifying his identity (say identity smart card available in some nations).
Suppose no Turing Test nor identification is done:
R = sqrt(E): attempt to reward average joe for mining more than BitCoin city heating rigs.
Average joe: downloads miner and will follow R=sqrt(E) for sizeable but not huge E
Greedy bastards: sybil attack compute many small E's (smaller than average joes), the derivative is higher than average joes with a sizeable E.
Now we have given greedy bastards an even bigger edge, and computing power and bandwidth etc still determine how many sockpuppets you can have solve tiny efforts. (in effect being rewarded linearly, if we recombine the many very small efforts at higher tangent)
Note how rewarding many small people promotes rigs, and makes for many accounts for the same person. in theory a slight deviation from linear reward in this sense could have the power to break up megapools...
R = E^2: punish small cpus and reward big rigs compared to linear reward: Only rigs and pools are worthwile, people tend to group and enlist under the same identity. Having pseudonymous accounts is a lossy business, performing effort under one name is more rewarding.
Note how there is a tradeoff between [Grassroots vs Centralization] and [one or multiple accounts]
Requiring an identity card signature for mining efforts could very well be used to reward average joe to promote wide quick adoption of currency, but would allow the goverment to produce fake identity signatures (not of real people since supposedly the private keys are generated on smart cards and never leave the card aherm...)
I also thought about what would happen if the proof of work was purely human: a mass pictionary game or something... and verification of blocks is done by human inspection

this would only be necessary during the introduction phase: we could organise a mass pictionary game during a few hilarious weeks and then many different humans would have coins that will never be replenished after which it could function just as bitcoin with miners safeguarding the network. There is a distinction between mining as a concept to distribute money and mining as a concept to secure the blockchain, I think few would honestly doubt their effectiveness for the latter, but a lot of people would have liked to see the introduction of money differently... oh well perhaps we just jealous fucks...
Can anyone think up a game that would be hard for a computer to play (probably with recognition and creativity)?
Perhaps a captcha solving game? I think the best captcha is making a captcha?