Why does radioactive material decay exponentially as opposed to at a constant rate?

Can anyone explain to me why exactly it is that radioactive material decays at an exponential rate? To make my confusion more clear, take the following example. Let's say you have 1 gram of radioactive material, and for the pure sake of argument, though I admit that I'm just pulling this number out of a hat, let's assume that 10 trillion radioactive atoms are in this gram. The half-life of this fictional radioactive material is 1 million years.

Now before I go any further, I just want to make it clear that I more or less understand the mathematics behind radioactive decay (N=N0 x e^-kt), so I don't need an explanation of that, or of how to use said formula.

Now, even though I know how to use that formula to calculate the amount left after n amount of time, I have always been completely baffled by the idea of it decaying exponentially. In other words, if you were to ask someone on the street who knew absolutely nothing about radioactive decay: "If you start with 1 gram of radioactive material, and after 1 million years it will have decayed to 0.5 grams, how long will it take for it to completely disappear?" I can almost guarantee that their answer will be 2 million years (that's what common sense would dictate), and for the life of me I have never been able to figure out why this would not be the case, because it is completely counter intuitive. Can someone explain to me what the mechanism is that makes radioactive decay an exponential process, as opposed to one that occurs at a constant rate? Do we even know?