Algorithm for finding "mean center" of unweighted graph
Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.

Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.

If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.

Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)