After talking with Mike Shaver and sending him some debug info, it turns out the problem is PAC files. Firefox runs all Proxy Auto-Configuration scripts synchronously, blocking the entire UI while things like DNS resolution run in JS (which is more noticeably painful over a slow connection).
Shaver says this won't be fixed until after FF3.
In the meantime, find another solution to your complex proxy rules... localhost proxy w/ PAC logic, ssh tunnels, etc.
As jesserud pointed out, it might be this bug, if you want to track it. (Update: And indeed, Shaver confirms that's the bug, and this comment says what needs to be done.)
Good to know what it is, at least.