So let's say I have some collection of variables $x_i$ each with their own uncertainty $\sigma_i$. (I'm trying to generalize this but if it helps, the $x_i$ themselves are a mean of other variables and $\sigma_i$ are the standard deviations of those means.)
Now I want to take the mean of these $x_i$ and compute the standard deviation on this mean. But I don't know how I should go about including the existing uncertainty in this calculation. My instinct says to just compute the propagated uncertainty of the mean and the standard deviation of the mean separately and then add those in quadrature, but I'm not sure if that's right.
So you want the standard deviation of $\frac{1}{n}\sum_i x_i ?$
I'll presume you intend that the $x_i$ are independent (though it's still doable if they aren't). One can show that for independent (or more generally uncorrelated) $x_i$ that $\operatorname{Var}(\sum_i x_i) = \sum_i \operatorname{Var}(x_i).$ So you have $$ \operatorname{Var}\left(\frac{1}{n}\sum_i x_i\right) = \frac{1}{n^2} \operatorname{Var}\left(\sum_i x_i\right) = \frac{1}{n^2}\sum_i\sigma^2_i$$
So the standard deviation is just the square root of this, which I believe matches your verbal description.