If you have some kind of expensive request, use fair queuing by IP address. If someone has a request pending, more requests from the same source go behind IP addresses with fewer requests. So each IP address competes with itself, not others.
For some reason, this isn't done much. I have it on a site of mine. I didn't notice for a week that someone was making a huge number of requests and not even waiting for the task to complete. It didn't hurt anything.