EDIT: I figured it out. I computed the Hessian incorrectly the first time (missed a crucial minus sign). Thanks to everyone who helped.
Suppose that we have two orientable regular surfaces, $A$ and $B$, such that $B$ is fully contained in the interior of $A$, and $A$ is has positive Gaussian curvature everywhere (for the purposes of this post, we can assume that $A$ is a sphere, even though $A$ is not necessarily a sphere in my problem).
Given a point $q\in A$, we find the point $p=p(q) \in B$ which is closest to $q$. Suppose further that we can find a $q \in A$ minimizes the distance $\Vert q - p(q) \Vert$ on $A$.
The problem: I would like to prove that the Gaussian curvature of $B$ at $p(q)$ is at least as great as that of $A$ at $q$.
I was thinking of taking two curves parametrized by arclength: $\alpha(t)$ on $A$ with $\alpha(0) = q$, and $\beta(s)$ on $B$ with $\beta(0) = p(q)$, and then using the fact that \begin{equation} \nabla (\Vert \alpha(t) - \beta(s) \Vert^2) |_{t=0, s=0} = 0, \end{equation} and \begin{equation} \det \left(\nabla^2 (\Vert \alpha(t) - \beta(s) \Vert^2) |_{t=0, s=0}\right) \geq 0, \end{equation} since $(q, p(q))$ minimizes $\Vert q - p(q) \Vert^2$ by construction. The gradient being zero allows me to conclude that, given that the minimal distance is not zero, the vector $q-p(q)$ is normal to both $\alpha$ and $\beta$ (which is expected due to our construction). In fact, I should be able to just take the normal vector to $A$ at $q$, which should also be normal to $B$ at $p$.
I was hoping that the inequality involving the Hessian would give me some fruitful inequality concerning the normal curvatures of $A$ and $B$ with respect to $\alpha$ and $\beta$, but I was unsuccessful in finding anything that would allow me to reach the wanted conclusion.
Could someone provide me with a hint on how to proceed, or suggest a different way to go about this?