To answer your question about the significance of restricted choice, and unpack that explanation, let's consider a simpler version of the example that Adam Sanjurjo and I shared with ESPN (we are following spaceisdarkgreen's lead here, but sticking with the approach in the ESPN article).
Imagine flipping a coin 3 times, and then selecting at random one of the flips that is immediately preceded by an $H$. You will select either flip 2 or flip 3, with equal chance. Let's say you selected flip 2 (analogous to flip 42). Well you know flip 1 is an $H$, because "preceded by $H$" was the selection rule. So you know you are in a sequence in which the outcomes of flip 1 and 2 are either $HH$, or $HT$. Why do we know $HT$ is more likely? Well, before flipping, the odds in favor of $HT$ relative to $HH$ were $1:1$, but the likelihood of selecting flip 2 (the flip we see) in world $HT$ is twice as likely when compared to world $HH$, because in world $HT$ you have to select flip 2 (i.e. $\mathbb{P}(flip\ 2|HT)=1$), whereas in world $HH$, you could selected flip 3 (i.e. $\mathbb{P}(flip\ 2|HH)=1/2$). So ex post, the odds in favor of $HT$ (relative to $HH$) double to $2:1$. With $2$ chances of $HT$ out of $3$ total chances, the probability of $HT$ becomes $2/3$, i.e. the probability flip 2 is a tails is $2/3$. This is Bayes rule, in odds form, which is simpler because it involves only multiplication. Dropping the verbiage, we have:
\begin{align}
\frac{\mathbb{P}(HT|flip\ 2)}{\mathbb{P}(HH|flip\ 2)}& = \frac{\mathbb{P}(flip\ 2|HT)}{\mathbb{P}(flip\ 2|HH)}\times \frac{\mathbb{P}(HT)}{\mathbb{P}(HH)} \\
& = \frac{1}{1/2}\times\frac{\mathbb{P}(HT)}{\mathbb{P}(HH)} \\
& = 2\times\frac{1/2}{1/2} \\
& = 2
\end{align}
This gives the intuition behind the bias (for flips that are not the final flip). You are more likely to select the flip you selected, flip 2, in the world in which it is a $T$, because in that world you have to, whereas in the world in which it is an $H$, you are less restricted in your choice as there are more other flips to choose from -- you could have selected the next flip, flip 3.
Note that if flip $3$ were selected, than for the world in which flip 2 and 3 are $HT$, the likelihood of you selecting flip 3 is the same as in the world in which flip 2 and 3 are $HH$, because $HT$ doesn't exclude flip 4 as a possibility, becase there is no flip 4 (we can ignore the first flip here). That means the odds don't change.
So considering all three flips, we have found that $\mathbb{P}(HT|flip\ 2) =2/3$ and $\mathbb{P}(HT|flip\ 3) =1/2$. Because each flip is equally likely to be chosen we have
$$\mathbb{P}(T|\text{flip preceded by $H$})= 1/2\times 2/3 + 1/2\times 1/2 = 7/12$$
Note 1: The ESPN example is from this general interest write-up of ours---while more complicated with longer streak lengths, it gives intuition about strength of bias as streaks get longer. The simpler version presented here can be found in a paper by Adam Sanjurjo and myself, which connects restricted choice to the hot hand and other conditional probability problems. We borrowed one popular way of communicating the intuition for why, in the classic Monty Hall problem, the contestant should update his/her beliefs when a door is opened (see this StackExchange for the details).
Note 2: The response of spaceisdarkgreen is a good one, along with the extra details in the comments, but it doesn't answer Barry's specific question. Spaceisdarkgreen's focus is on the sampling distribution of the proportion and the calculation certainly demonstrates that the measure is biased, but it doesn't give an intuition for the direction of the bias.
Best Answer
Given a fair coin, the number of heads (in $1000000$ flips) has a binomial distribution with a mean of $500000$, but it is very close to being normally distributed with that same mean, and with a standard deviation of
$$ \sigma = \sqrt{1000000 \left(\frac{1}{2}\right) \left(\frac{1}{2}\right)} = 500 $$
Using the usual properties of the normal distribution, we find that the number of heads should be within $500$ (one sigma) of $500000$ about $68$ percent of the time, within $1000$ (two sigmas) about $95$ percent of the time, and so on.
ETA: (Semi-)fun fact—The probability that we are outside one sigma is approximately $\frac{1}{\pi}$; the probability that we are outside two sigmas is about $\frac{1}{7\pi}$; the probability that we are outside three sigmas is about $\frac{1}{16e^\pi}$.