EDIT AT BOTTOM
The real answer is more complicated than this, but suffice to say, there's a statistical "hump" you have to get over. That is to say, there's a point at which all of the pixels have been sampled enough times that they are at least close to the right value. At that point, more samples will clear things up. Before you reach that "hump," Cycles is still finding all the things that might contribute to the color of each pixel. There will still be lots of pixels that are way off because their first few samples just so happened to be really bright, and it will take more samples to bring them back down to a realistic level.
Here's a bit more of an explanation. It's not very technical, but it is correct. I generally think it's easier to think about it this way than the technical way. You might not, but here goes...
It can be useful to think of Cycles as though it were taking a statistical average of what color each pixel ought to be. Cycles sends out a ray. That ray hits a very bright spot, so it makes that pixel very bright... but Cycles has no way of knowing that the very bright spot is right next to a much darker spot, until it sends out another ray that DOES hit that dark spot. So now it averages the bright pixel it had before with this new dark value and it gets a little closer to the correct color. Until Cycles has enough data to get a reasonably accurate average for most of the pixels, you'll have a bunch of "outliers."
It's a little like if you wanted to calculate the average population per city in the US, but you could only do it one city at a time. If you start your calculations with a city like Wheelock, TX, then your computed average is going to be 350 because that's how many people are in Wheelock. You have to get the populations of more and more cities before your computed average starts to look like the real average. It's the same with Cycles. It's averaging multiple samples per pixel. Some samples are super bright, and not very close to the real average for that pixel. So you're going to have a super bright (or dark) pixel until Cycles gets enough data to bring that pixel down closer to where it's really supposed to be.
There is also another contributing factor. You can (almost) always get brighter, but you can only get so dark. So, it's possible to have a dark pixel that's much darker than it should be (the opposite of a firefly), but the darkest it can possibly be is zero. On the other hand, if you've got a 100000 watt light source somewhere in your scene, it's possible for a sample to hit that source directly. and now you have a single pixel that's 100000 "brightnesses" or so. It will be much harder to average down that very bright pixel to a more correct brightness than to average up the 'zero' pixel. Even if the next sample is only a 1, when you average that with the 100000, you still have a pixel that's 50000 "brightnesses." This means that fireflies are easier to produce than "blackholes," but they're also more persistent than "blackholes." This is what
Clamp Direct and
Clamp Indirect are for. This is your way to tell Cycles "let's say that 100000 brightness pixel is only 100," so that it's much easier to average out. But it's really easy for that clamping to make things inaccurate, if you're too aggressive with it.
NOW, as for HDRIs, it's a simple matter of having a much larger dataset to sample. With a larger dataset, it's much more likely that any given sample will NOT be close to the correct average, resulting in more grain, rather than less.
Hope that helps!
EDIT: One very good solution to fireflies is actually to render the same image several times, but with a different "seed" value for each one. Then average these images (careful with the opacity math!) together in an image editor. When you save out the file, the 1000000 watt pixel will have to be 1, which is much easier to average with the corresponding pixel from another version of the image that maybe doesn't have that firefly because it sampled differently.