On math.stackexchange we find that a variation of the connection $\Gamma_{\nu\sigma}^\rho$ (not a tensor) is a tensor (it obeys the the tensor transformation equation).
On physics.stackexchange we find that $\delta g_{\mu\nu} = -g_{\mu\rho}g_{\nu\sigma}\delta g^{\rho\sigma}$. So a variation of the metric (a tensor) is not a tensor (it does not obey the rule about raising and lowering indices).
This seems like a minefield. Do I have to check the tensor-ness of every object I vary? Or is there some rule?
You have to handle everything on a case by case basis, but you don't always have to go back to the tensor transformational law. The trick is to remember a few results, such as that $\delta\nabla_aX=\nabla_a\delta X$ and $\delta\partial_aX=\partial_a\delta X$ (and that $\nabla$ sends tensors to tensors, as can be proven from their definition), $\delta(XY)=X\delta Y+(\delta X)Y$, and $\delta\delta_a^b=0$. Thus$$\Gamma_{ab}^cV_c=(\partial_a-\nabla_a)V_b\implies\delta\Gamma_{ab}^c\cdot V_c+\Gamma_{ab}^c\delta V_c=(\partial_a-\nabla_a)\delta V_b=\Gamma_{ab}^c\delta V_c\implies\delta\Gamma_{ab}^c\cdot V_c=0.$$Finally, this contraction with arbitrary vectors to form a (vanishing) rank-$2$ tensor implies $\delta\Gamma_{ab}^c$ transforms as a tensor (again, this is easily verified from the definition). By contrast, when no obvious proof a quantity transforms as a tensor can be obtained with such tricks, it's worth trying to prove the opposite from the definition, as you can with the second example you gave.