First, some corrections.
The left side is a tensor, but each component of the right side is not by itself a tensor
You meant "each term on the right hand side", right? Components of tensors (or nearly tensors) of course never transform as tensors themselves. A component is one number that you may obtain by choosing a value of the index $\mu$ etc., for example $V_0$. That's never a tensor. The objects $a,b$ in the expression $a+b$ or perhaps $a-b$ are called terms.
Now, when you say that the averaged Heisenberg equation comes "directly from classical mechanics", it sounds strange. A quantum mechanical equation can't "come directly from classical mechanics" because quantum mechanics isn't a part of classical mechanics in any sense; it's a more general theory. A more correct statement of this sort is exactly the opposite one: the classical counterpart of the quantum equation you wrote – one that involves Poisson brackets – may be directly derived from quantum mechanics. Classical mechanics is a limit of quantum mechanics; that's the only legitimate and exact relationship between the two theories. On the other hand, a quantum theory can't be generally obtained "directly from a classical theory" and the same thing holds for all of its objects and equations.
Now, yes, the modification of derivatives by extra terms is something that is omnipresent in physics. It's so omnipresent that you shouldn't overstate the impact of the mathematical similarity. For example, you wrote the covariant derivative in GR. There's an even more similar object, a covariant derivative in gauge theories such as electromagnetism
$$\nabla_\mu = \partial_\mu +i e\cdot A_\mu$$
Here, the extra term is proportional to the electromagnetic potential rather than the Christoffel symbol $\Gamma$ from your example. Despite this similarity in the required maths, there is no simple way to unify gauge theories with gravity. The differences – e.g. in the number of indices in $\Gamma$ and $A_\mu$, aside from deeper differences – are substantial so that if one tries to develop the whole theories, things don't work for gravity in the same way as they work for gauge theories.
Now, yes, the total derivative of an operator in quantum mechanics may be obtained from calculating the partial derivative – the explicit dependence on $t$ that is written as a part of the definition of the operator (that's the last term on the right hand side, often equal to zero because we study "operators whose definition is constant in time") plus an extra term proportional to $[A,H]$ (you wrote expectation values but you didn't have to: the equation holds for whole operators, too) which is remotely analogous to the connection term with $\Gamma$ and/or $A_\mu$.
And yes, one can say many related facts about the reasons why these extra terms appear and why they're analogous in both situations. In general, the connection terms in the "total/covariant" derivatives are there because they relate the "tangent or internal spaces" at one moment of time (or spatial coordinates) and the nearby, infinitesimally distant moment of time.
In the case of your general relativistic example, one relates the tangent bundles/spaces (and/or the cotangent ones). When you try to shift a vector (or tensor) from one point of spacetime to a nearby point where the metric is different, it's natural to rotate the components a little bit depending on the change (first derivative) of the metric i.e. depending on $\Gamma$ (which depends on the first derivatives of the metric and of course the metric itself). The most natural way to "shift" a vector to a nearby point is the parallel transport. The covariant derivative measures how the actual field $V_\mu$ etc. changes with the spacetime coordinates when you remove the "normal" change that is expected by the parallel transport, i.e. when you add the $\Gamma$ connection terms.
Similarly in electromagnetism and Yang-Mills theories, one may naturally "parallel transport" a charged field to a nearby point. It's natural for the phase to change by $e\cdot A_\mu dx^\mu$. Again, the covariant derivative expresses how much the actual field changes differently than what is expected from the $A_\mu$-dependent parallel transport. This difference – some kind of an "anomaly" in the colloquial sense – is a more natural object than the simple partial derivatives. It also transforms "covariantly", an analogy of its being a tensor.
Finally, in the Heisenberg quantum equation example, the natural shift from one moment $t$ to the nearby moment $t+dt$ is accompanied by a transformation on the Hilbert space by $1+i\cdot dt\cdot H/\hbar$. This gradual "unitary transformation/rotation" of the Hilbert space is what we see in Schrödinger's equation, too. In the Heisenberg equation, we observe the derived action on the operators – because $H$ acts both on kets and bras, the action of this infinitesimal rotation on operators is represented by the commutators $[A,H]$, the analogy of $H\psi$. The Heisenberg equation simply says that the operators evolve "naturally" according to the explicit dependence as well as the "connection terms" – and the connection terms relating nearby moments of time are proportional to the Hamiltonian in this case.
If you view the examples in your question as really analogous, you may say that they appear anywhere in physics where there are certain "real or abstract spaces" that are attached to each moment of time – or each point in the spacetime or perhaps another space – but they may be attached in various rotated ways and one is forced to study whether the "rotations done before the attachments" are done differently at two nearby points of the time or spacetime. But because pretty much everything in physics depends on some continuous variables (time, space etc.) and spaces with symmetries are also omnipresent in physics, the appearance of the "analogy" of the covariant derivative is guaranteed to be quite universal, too. This is one similarity but there are tons of respects in which the situations or subfields of physics differ and you can't overlook those, either.