Would predictable statistical distribution of complexity not be enough? As in, you get a randomly assigned job, that takes on average a given amount of processing power, and is proven to not need more than some upper limit - or even, you time out after a given amount of processing power and request a new job. And ideally have each unit small enough that mining will completing multiple jobs so difference in complexity starts averaging out.