Algorithm for getting symetric vertex sets of undirected graph
You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from which you can easily compute the orbits of its action on the vertices.

Solving GI using your task. Given connected graphs $G_1,G_2$, we want to know whether they are isomorphic. Compute the orbits, and check whether any of them mixes vertices from $G_1$ and $G_2$.

Solving your task using GI. Given a graph $G$ and two vertices $x,y$, create two copies of $G$ and attach a long path to $x$ in one of them and to $y$ in the other. The two vertices belong to the same orbit if these graphs are isomorphic.

The second reduction involves $n^2$ invocations of GI, whereas $\log B_n \approx n\log n$ (here $B_n$, the $n$th Bell number, is the number of partitions of $\{1,\ldots,n\}$). This means that any reduction needs $\Omega(n\log n)$ invocations of GI, and suggests that my reduction can be improved.