What about simultaneous solving of a captcha?
Or flipping things around so that the Sybil is creating a social good.
e.g. If you have a mesh network, the more nodes the more resilient and stable the network is.
So you can create as many nodes as you want, but each one comes at a cost and has a disproportionate benefit to the wider network.
Perhaps you could have geographically dispersed wifi nodes giving away cash at x/units a second. The rate would be based upon how geographically isolated one node is from it’s nearest neighbour and the population density of the area. Your phone would connect to these nodes (verifying their existence) as you go about your day and collect the cash, so that on average as you travel around in a week you will receive approximately the basic income from a diverse set of nodes.