Given spherical coordinates on a unit sphere, imagine a spherical quad defined by two ranges $[\phi_0,\phi_1]$ and $[\theta_0,\theta_1]$. If you have a globe, for example, the grid formed by the latitude and longitude lines is composed of the kind of quads I'm talking about.
I need to generate a random vector on the surface of this quad. I think the quads decrease in area sinusoidally toward the poles, so I think maybe I could figure something out, but I was wondering if such an algorithm already exists, before I go trying to reinvent any wheels.
Rahul's comment exploits a peculiar feature of two-dimensional sphere: the spherical area bounded between two parallel planes is proportional to the distance between them. (See here). This is why we can sample points uniformly on unit 2-sphere by choosing cylindrical coordinates: $z$ uniformly from $[-1,1]$ and longitude $\theta$ uniformly from $[0,2\pi]$. (The latitude is then calculated from $z$.)
Restriction to the rectangular region is accounted for by restricting $\theta$ and $z$ accordingly. For a more complex shape one could use the usual process of generate - check - reject if outside.