I think Izotope RX is definitely the more powerful audio cleaner in its price range. Although i'd like to hear the software/hardware of choice for forensic audio guys; does anyone here do that?
As for times, here's an example. I recently had to clean up some horrible audio on a deposition tape. What they delivered to me had loud LOUD hums, a high noise floor, only a few of the people in the room had lapels, and it was all in a horribly compressed mpeg codec with no information above 6k. In about an hour, using RX, i found the hums and removed them; took a sample of the hiss/noise floor and ran that through the denoiser, as well as some eq and multiband expansion with Waves C4. A few volume rides, and i recorded it out. I could have taken a lot longer to finesse my settings, but it was never going to sound anywhere near "good", so i made it intelligible and went no further.
The main problem i heard in the interview you posted seemed to be some hum towards the end; izotope RX has a hum removal module that i think would nail that. Apparently in RX2, the hum removal module actually identifies the frequency of the hum for you, and even recommends if the denoiser module would be more effective! As for the traffic bg, the denoiser could take a fair bite out of that. I don't know if the guy says anything after he's demiked himself, and that would be very hard to bring out of the noise floor. But hey, they could just use what they can from the interviewer's mic. There are definitely quick and dirty ways of cleaning things, if time is an issue.