How many vertices of degree exactly $\lfloor n/2 \rfloor$ does the random graph $G(n,1/2)$ contain?
My calculations show that asymptotically this number is around $n^{1/2}$ but I feel like I have made a mistake somewhere.
Let $n = 2m+1$ (for easier notation). $$\mathbb{P}(deg(v)=m) = {2m \choose m} (1/2)^{m}(1/2)^{m}$$ since we choose the $m$ neighbours of $v$ from the remaining $2m$ vertices. If the random variable $X$ counts the number of vertices of degree exactly $m$, $$\mathbb{E}X = (2m+1){2m \choose m}(1/2)^{2m}$$ Using the bound $m^{1/2}{2m \choose m} \geq 2^{2m-1}$ (for large enough $m$), $$\mathbb{E}X \geq 2m^{1/2}2^{2m-1}(1/2)^{2m} = m^{1/2}$$
Is this correct? $m^{1/2}$ seems like too large a number but I am unable to find a mistake.
Around $n^{1/2}$ is exactly what we expect.
Your calculation is fine: for a sharper estimate, we can use Stirling's approximation. This gives us $$ \Pr[\deg(v) = m] = \binom{2m}{m} 2^{-2m} = \frac{(2m)!}{(m!)^2 2^{2m}} \sim \frac{\sqrt{4\pi m}\left(\frac{2m}{e}\right)^{2m}}{\left[\sqrt{2\pi m}\left(\frac{m}{e}\right)^m \right]^2 2^{2m}} = \frac{1}{\sqrt{\pi m}}. $$ So the expected number of vertices of degree $m = \frac{n-1}{2}$ is $\frac{2m+1}{\sqrt{\pi m}} \sim \frac{n}{\sqrt \pi}$.
A similar estimate with a slightly messier proof holds when $n$ is even and $m = \frac n2$ or $m = \frac{n}{2}-1$.
General intuition is that the symmetric binomial distribution $\text{Binomial}(n, \frac12)$ assigns significant probability only to the $O(\sqrt n)$ points around the mean $\frac n2$. Formally, for any $\epsilon > 0$, there is a $C$ such that the probability of leaving the interval $(\frac n2 - C \sqrt n, \frac n2 + C\sqrt n)$ is less than $\epsilon$. The same thing should hold for asymmetric binomial distributions where the probability $p$ is not too small or too large.
We can see this in a bunch of ways. For example, it follows from Chebyshev's inequality, because the standard deviation of the symmetric binomial distribution is $\frac12\sqrt n$, and the probability of going more than $k$ standard deviations from the mean is at most $\frac1{k^2}$.
The relationship between $C$ and $\epsilon$ that Chebyshev gives is not too sharp. Hoeffding's inequality or the normal approximation make more precise predictions.
Anyway, if the binomial random variable is in the interval $(\frac n2 - C \sqrt n, \frac n2 + C\sqrt n)$ with probability close to $1$, and $\frac n2$ is the likeliest value in that interval, its probability should be at least $\frac1{2C\sqrt n}$, which is why the $n^{1/2}$ in your observation appears.