After seeing the answer above, I was able to mostly solve the problem. There was an issue, however, in that the sign of $\theta$ is always positive when you actually go through the whole solution--calculating the vectors, then $\phi$, then $\theta$ using the law of sines.
So the issue is: which side of the character face vector is the enemy direction vector (assuming the character is facing the enemy). There doesn't seem to be a trivial way to figure this out, given two arbitrary vectors, using the tools a computer has.
The simplest, most straight forward way that I found to accomplish this--without any kind of logic or pattern recognition--was to just use the sign of the determinant of the two vectors--so $\operatorname{sign}(x_1*y_2 - y_1*x_2)$. The asymmetry gives you a left and right with only 2 multiplies and a subtraction (important when you are in a game loop that is doing 120 fps).
Anyhow, here is how it worked out:
In order to calculate $\phi$ in the drawing above, I used the dot product:
$$
\mathbf{A}\bullet\mathbf{B} = ||A||\operatorname{cos}\phi
$$
Where $\mathbf{A}$ is the unit vector pointing from the enemy to my character (in the drawing), and $\mathbf{B}$ is the unit vector pointing in the enemy's direction of travel.
Having solved for $\phi$ by taking the $\operatorname{arccos}$ of the dot product result, I calculated $\theta$ in the drawing above with the law of sines,
$$
z*t*\operatorname{sin}\theta = s*t*\operatorname{sin}\phi\\
\theta = \operatorname{arcsin}(\frac{s}{z}\operatorname{sin}\phi)
$$
But there was a problem: $\theta$ was always positive. The issue was the range of the $\operatorname{arccos}$ function: $[0,\pi]$. As a result of the $\operatorname{arccos}$ range, $\phi$ was always positive, and the character would only lead the enemy when the angular velocity of the enemy relative to the character was positive.
So, in order to recapture the "sign" of the angle, I think that what you need is the sign of the determinant of the two vectors (did not find an authority or proof...just thought about it and tested).
So,
$$
\theta' = \operatorname{sign}(\operatorname{det}
\begin{bmatrix}
A_x & A_y \\
B_x & B_y
\end{bmatrix}
) * \theta
$$
Will give you back the "sign" of the angle.