Solution:

The path Theseus traces out is a closed, non-self-intersecting path in the plane. Since each move is along a line segment, the path forms the boundary of a polygon in the plane. WLOG this polygon is traversed counterclockwise (i.e. with the interior of the polygon always on Theseus's left); the argument in the clockwise case is analogous, with a sign flip.
Let $i=0$ correspond to the direction east, $i=1$ correspond to north, and so forth. For $0 \leq i \leq 3$ and $j=i \pm 1$ let $X_{ij}$ be the number of times Theseus switches from going in direction $i$ to going in direction $j$ (where indices are taken $\bmod\ 4$). So, $X=X_{1,2}$, $Y=X_{2,1}$. We have the following relations among the $X_{ij}$:
The sum $n=\sum X_{i, j}$ is the number of vertices of the polygon. The sum of the interior angles of the polygon is thus $\pi(n-2)$. Each counterclockwise turn contributes $\frac{\pi}{2}$, and each clockwise turn contributes $\frac{3 \pi}{2}$ to this sum. The number of the former is counted by $\sum X_{i, i+1}$, and the latter by $\sum X_{i+1, i}$. So, $\pi(n-2)=\frac{\pi}{2} \sum X_{i, i+1}+\frac{3 \pi}{2} \sum X_{i+1, i}=\pi n+\frac{\pi}{2} \sum\left(X_{i+1, i}-X_{i, i+1}\right)$, which gives $\sum\left(X_{i, i+1}-X_{i+1, i}\right)=4$.
Finally, observe by starting from the middle of any edge that since we start and end in the same direction, the number of times we turn into direction $i$ must equal the number of times we turn out of it. So $X_{i, i+1}+X_{i, i-1}=X_{i+1, i}+X_{i-1, i}$, which rearranges to give $X_{i, i+1}-X_{i+1, i}=X_{i-1, i}-X_{i-1, i}$. So $4=\sum\left(X_{i, i+1}-X_{i+1, i}\right)=4\left(X_{1,2}-X_{2,1}\right)=4(X-Y)$.
So $X-Y=1$ as desired.