One approach would be to use a k-d tree. You can use the k-d tree to answer the following query:
Input: $x \in S$, $0 \le \theta < 2\pi$.
Output: The number of points $y \in S$ such that the angle between a vertical line through $x$ and a line from $x$ to $y$ is at most $\theta$.
A procedure for answering Count queries can be used to answer your queries, through binary search on $\theta$.
To answer Count queries with a k-d tree, note that each node of the k-d tree corresponds to a region $R$ of space. Augment each node with the number of points in that region (a one-time preprocessing). Now, when answering queries, recursively traverse the tree. If $x \notin R$, and either all of $R$ makes an angle with $x$ that is $\le \theta$ or all of $R$ makes an angle that is $>\theta$, you don't need to recurse into that node of the k-d tree; you can just use the count associated with that node. Otherwise, recurse. You can tell whether this condition holds by computing the angle from $x$ to each corner of $R$. This gives you a procedure for answering Count queries more efficiently than enumerating all points in $S$.
I don't know what the worst-case asymptotic running time will be, but it might be a pragmatic solution. I don't know if you can efficiently answer your queries directly on the k-d tree rather than working indirectly via Count queries.