Below is the Spherical Law of Cosines as it appears in UCSMP Functions, Statistics, and Trigonometry, 3rd ed., copied here because the diagram is good and helps with clarity.

If $\triangle ABC$ is a spherical triangle with arcs $a$, $b$, and $c$ (meaning the measures of the arcs, not the lengths), then $\cos c=\cos a\cos b+\sin a\sin b\cos C$.
Now, to the specific problem at hand. Let's use the diagram below, also from UCSMP Functions, Statistics, and Trigonometry, 3rd ed., for reference.

Let $A$ and $B$ be as you defined them. $N$ and $S$ are the north and south poles, respectively; $C$ and $D$ are the points on the equator that are on the same line of longitude as $A$ and $B$, respectively. Consider spherical $\triangle ABN$. $a=(90°-\text{latitude of point }B)$; $b=(90°-\text{latitude of point }A)$. $N=\text{positive difference in longitude between points }A\text{ and }B$. Use the Spherical Law of Cosines ($\cos n=\cdots$ form) to determine $n$, which is the shortest arc between the two points.
(graphics from Lesson 5-10 of UCSMP Functions, Statistics, and Trigonometry, 3rd ed., © 2010 Wright Group/McGraw Hill)