Why is mutual information symmetric? I know that mutual information is the Kullback-Leibler divergence between $p(x,y)$ and $p(x)p(y)$. But mutual information is also described as the amount of entropy lost (or, in another sense, the information gained) about $X$ by virtue of knowing about $Y$.
Without just looking at the formula, it's not clear why the additional info about $X$ due to having $Y$ would be the same as the additional information about $Y$ due to having $X$. It's not immediately obvious that predicting $Y$ from the behavior of $X$ is just as easy as predicting $X$ from the behavior of $Y$. While "mutual" is in the name, mutual information is described in terms of learning about $X$ using Y, and so in the same way that e.g. KL divergence (which is described in terms of describing $X$ using $Y$) is asymmetric, the intuition for me would have been that "mutual" information is asymmetric too.
Is there any intuition here without just looking at the formula for $I(X;Y)$?

You are correct that the $MI$ is the KL-Divergence between the joint $p(x, y)$ and factored marginal distributions $p(x)p(y)$. With the KL-Divergence telling us "how similar" the two distributions are. So, what $MI$ is measuring is the amount of information gain if we update from a model that treats the two variables as independent $p(x)p(y)$ versus one that models the variables joint probability density $p(x, y)$.
If one models the true joint probability density, then we also have access to conditional probability distributions $p(x|y)$ where I like to think of these as "given $Y = y$", how does the distribution of $X$ change? Or, given $X = x$, how does the distribution of $Y$ change? Given we are modeling the joint and factored marginal distributions, we can then re-express $MI$ in terms of joint and conditional entropies:
$I (X; Y ) = H (X) − H (X|Y ) = H (Y ) − H (Y |X)$
Therefore, we can interpret the $MI$ between $X$ and $Y$ as the reduction in uncertainty about $X$ after observing $Y$, or, by symmetry, the reduction in uncertainty about $Y$ after observing $X$
