I suspect they pull down the data for whether a cron needs to be run in an initializing query that also pulls down a ton of other data (site name, for example). So in theory, they're only doing a few time comparisons of extra work per request.
Also - I haven't looked too deep into WP's implementation, but are they actually doing it on page load? I've seen it in other php software (I believe phpBB) as a 1px image. This kinda solves the caching issues others are talking about...your server might still get hung up, and that picture might never load, but if you're cached properly I think it won't stop anyone from reading.
Ignoring the bugs though...I've had my shared hostgator plan handle a couple of top page HN post with no additional caching installed, which makes me think it's probably not a problem for most people running WP. (I just double checked to make sure that's actually true, and it is.)