I am trying to minimize the difference between two normalized vectors of dimension $N$. Currently, I am using an $L_2$ normalized distance.
Since the vectors are normalized, they should sit on some hypersphere. Hence, it doesn't seem to make sense to use the Euclidean metric. Rather, I should use something that takes the distance to "walk on" that hypersphere, but not "through" it. What metric should I use?
If I understand correctly, you have two subsets $A,B$ of the sphere in $\mathbb{R}^N$ (where sphere is the set of norm $1$ vectors with respect to the normalized $L_2$ norm, I gather). You are trying to find $\inf_{x\in A, y\in B} d(x,y)$ and your question is asking what distance $d$ corresponds to the shortest path that stays on the surface of the sphere instead of going inside of it. The metric you are looking at is the geodesic distance on the sphere (and in general, shortest path metrics are called geodesic distance).
However, if you solve the problem of finding $u\in A$ and $v\in B$ such that $\|u-v\|=\inf_{x\in A, y\in B}\|x-y\|$, where $\|\cdot\|$ is the normalized $L_2$ norm, the same pair of points will minimize the geodesic distance. Indeed, for two pairs of points $(u,v)$ and $(x,y)$ on the sphere, the walking distance between $u$ and $v$ on the surface of the sphere is less than (or equal to) the walking distance between $x$ and $y$ on the surface of the sphere if and only if the direct ($L_2$) distance between $u$ and $v$ is less than (or equal to) the direct ($L_2$) distance between $x$ and $y$. More specifically, if you know one of the distances (walking/$L_2$) between $u$ and $v$, you can find the other. Since both distances are invariant under orthogonal transformations, you can assume that $u$ and $v$ are both on the circle in $\mathbb{R}^2$ (by applying a suitable orthogonal transformation).