How can I prevent deduping from killing my server?
I think Parvez's work on deduplication performance is a big piece of this puzzle: http://vedaconsulting.co.uk/civicrm-dedupe-workflow-ui (see step 1).  Some of the answers here are also relevant to improving performance.

However, neither of these solves what's probably your most common use case - someone running a massive deduplication script.  One solution might be to feed deduplication into a queueing system.  Another might be to permission the dedupe screen - or even permission specific dedupe jobs, so that someone can run Parvez's smart dedupe but not a standard dedupe rule.