$ \operatorname{Var}(X) = E[X^2] - (E[X])^2 $
I have seen and understand (mathematically) the proof for this. What I want to understand is: intuitively, why is this true? What does this formula tell us? From the formula, we see that if we subtract the square of expected value of x from the expected value of $ x^2 $, we get a measure of dispersion in the data (or in the case of standard deviation, the root of this value gets us a measure of dispersion in the data).
So it seems that there is some linkage between the expected value of $ x^2 $ and $ x $. How do I make sense of this formula? For example, the formula
$$ \sigma^2 = \frac 1n \sum_{i = 1}^n (x_i - \bar{x})^2 $$
makes perfect intuitive sense. It simply gives us the average of squares of deviations from the mean. What does the other formula tell us?

The other formula tells you exactly the same thing as the one that you have given with $x,x^2$ $\&$ $n$. You say you understand this formula so I assume that you also get that variance is just the average of all the deviations squared.
Now, $\mathbb{E}(X)$ is just the average of of all $x’_is$, which is to say that it is the mean of all $x’_is$.
Let us now define a deviation using the expectation operator. $$Deviation = D = (X-\mathbb{E}(X))$$ And Deviation squared is, $$D^2 = (X-\mathbb{E}(X))^2$$
Now that we have deviation let’s find the variance. Using the above mentioned definition of variance, you should be able to see that
$$Variance = \mathbb{E}(D^2)$$ Since $\mathbb{E}(X)$ is the average value of $X$,The above equation is just the average of deviations squared.
Putting the value of $D^2$, we get, $$Var(X) = \mathbb{E}(X-\mathbb{E}(X))^2 = \mathbb{E}(X^2+\mathbb{E}(X)^2-2X*\mathbb{E}(X)) = \mathbb{E}(X^2)+\mathbb{E}(X)^2-2\mathbb{E}(X)^2 = \mathbb{E}(X^2)-\mathbb{E}(X)^2$$ Hope this helps.