I've seen several "proofs" of this formula, all of which proceed by a sequence of randomly-chosen algebraic operations and end at the famous formula. Of course, no normal human being would ever pluck these out of thin air like that.
For me, the realization was this: Consider the formula
$$(x - \alpha)(x - \beta) = 0$$
If $x=\alpha$, then $x-\alpha$ is obviously zero. Whatever $x-\beta$ happens to be, it gets multiplied by zero, so the result is still zero. So in other words, one solution to this equation is $x=\alpha$. By a similar line of reasoning, $x=\beta$ is also a solution. So here we have purposely constructed an equation that has exactly two solutions: $\alpha$ and $\beta$ (which can be whatever we choose them to be).
Now let's open the brackets:
$$(x-\alpha)(x-\beta) = 0$$
$$x(x-\beta) - \alpha(x-\beta) = 0$$
$$x^2 - \beta x - \alpha x + \alpha \beta = 0$$
$$x^2 - (\alpha + \beta)x + (\alpha \beta) = 0$$
Now suppose we have an equation that looks like
$$x^2 + Ax + B = 0$$
(Notice that this isn't the usual general quadratic equation. I've assumed that the $x^2$ has a coefficient of 1.)
If we line the two equations up, it becomes clear that
$$A = -(\alpha + \beta)$$
$$B = (\alpha \beta)$$
This is the direct relationship between the coefficients we can see, and the solutions we want to find. Now, how to figure out the solutions from the coefficients?
We know that $-A$ is the sum of the solutions, and $B$ is the product of the solutions. But what are the solutions themselves? Hmm.
Well, if $-A$ is the sum, then $-A/2$ is the arithmetic mean of the solutions. I.e., it's exactly half way between the two solutions. Great, if we can just figure out how far apart the solutions are, we could exactly compute them!
So we have the sum and the product, but we want the difference. Hmm. OK. But how do we do that?
We've got $\alpha + \beta$ and we've got $\alpha \beta$, but we want $\alpha - \beta$. Tricky…
The solution is Black Magic. Observe: The thing we have is $\alpha + \beta$, and
$$(\alpha + \beta)^2 = \alpha^2 + 2 \alpha \beta + \beta^2$$
The thing we want is $\alpha - \beta$, and
$$(\alpha - \beta)^2 = \alpha^2 - 2 \alpha \beta + \beta^2$$
The difference between these two expressions is exactly $4\alpha\beta$ — which we can compute! If $B = \alpha\beta$, then $4B = 4\alpha\beta$. What I am saying is that
$$(\alpha - \beta)^2 = (\alpha + \beta)^2 - 4\alpha\beta = A^2 - 4B$$
It therefore follows that
$$\alpha - \beta = \sqrt{A^2 - 4B}$$
Recalling that $-A$ is the sum of the solutions and so $-A/2$ is the average, we have
$$\alpha = -\frac{A}{2} - \frac{\sqrt{A^2 - 4B}}{2}$$
$$\beta = -\frac{A}{2} + \frac{\sqrt{A^2 - 4B}}{2}$$
In other words, half the sum minus half the difference gives the lower solution, and half the sum plus half the difference gives the upper solution.
$$x = \frac{-A \pm \sqrt{A^2 - 4B}}{2}$$
Notice that this doesn't look quite like the familiar formula, because we assumed that the $x^2$ coefficient equals exactly 1. But notice that if we divide all the coefficients by the leading one, we can get this form!
$$ax^2 + bx + c = 0$$
$$x^2 + \frac{b}{a}x + \frac{c}{a} = 0$$
$$A = \frac{b}{a}$$
$$B = \frac{c}{a}$$
Substitute these into our previous formula, and (trust me) the familiar quadratic solution formula pops out.
Notice that we can do this trick for a polynomial of any degree!
$$(x - \alpha)(x - \beta)(x - \gamma) = 0$$
This gives a cubic equation with known solutions. Opening the brackets,
$$x^3 - (\alpha + \beta + \gamma)x^2 + (\alpha\beta + \alpha\gamma + \beta\gamma)x - (\alpha \beta \gamma) = 0$$
Given the equation
$$x^3 + Ax^2 + Bx + C = 0$$
we get
$$A = -(\alpha + \beta + \gamma)$$
$$B = (\alpha\beta + \alpha\gamma + \beta\gamma)$$
$$C = -(\alpha\beta\gamma)$$
The trouble is, now we need to somehow compute $\alpha$, $\beta$ and $\gamma$ given only $A$, $B$ and $C$. And it turns out this is way harder than last time. (Indeed, I have no damn idea how to do it! Computing the average doesn't really help this time.)