If (x,y,z) is a point on the surface of the unit sphere centered at the origin, the East vector is something like (z, 0, -x) and the North vector is something like (-xy/S, S, -yz/S), with S:=sqrt(1-y^2). You can then express your direction as North * cos(angle) + East * sin(angle).

I kind of rushed through the Math, so I am not 100% certain that the formulas are correct, but you can try to reproduce them yourself.