Say $Y_i$ is real-valued. Then $E[Y_i|X_i]$ gives us, for each specific $X_i$, a real number. In what way is this random?
Your first two sentences are entirely correct, so think about the implication of this. This means that the conditional expectation is a function mapping each possible outcome of $X_i$ to a real number. Thus, if we let $\mathscr{X}$ denote the range of possible values of $X_i$ then there is some function $h:\mathscr{X} \rightarrow \mathbb{R}$ such that:
$$\mathbb{E}(Y_i|X_i) = h(X_i)
\quad \quad \quad \quad \quad
\mathbb{E}(Y_i|X_i=x) = h(x).$$
So, we have established that the conditional expectation is a function of the conditioning variable. In the first of the two cases shown in the above equations, the conditioning variable is treated as a random variable, so our function of that variable is also random.