Is any "spring-like" embedding of interest to you? I wonder how fast would it be to get the vertex coordinates for the graphs you consider using Graphviz.

I suppose it takes time because the SpringElectricalEmbedding layout requires an optimization with a very large number of parameters.

I agree with Gianluca. I don't think Graph[g, GraphLayout->"SpringElectricalEmbedding"] actually computes the vertex coordinates. I think it sets an option that determines how they are to be computed, whenever they are needed.

One may infer this, I believe, from the following small example:

g = RandomGraph[{8, 12}];
g = Graph[g, GraphLayout -> "SpringElectricalEmbedding"];
g // InputForm
(*
Graph[{1, 2, 3, 4, 5, 6, 7, 8}, 
 {Null, SparseArray[Automatic, {8, 8}, 0, 
   {1, {{0, 1, 5, 8, 10, 13, 17, 21, 24}, {{6}, {3}, {4}, 
     {5}, {6}, {2}, {6}, {7}, {2}, {7}, {2}, {7}, {8}, {1}, 
     {2}, {3}, {8}, {3}, {4}, {5}, {8}, {5}, {6}, {7}}}, 
    Pattern}]}, {GraphLayout -> {"Dimension" -> 2, 
    "VertexLayout" -> "SpringElectricalEmbedding"}}]
*)

We can calculate the coordinates like this:

GraphEmbedding[g]
(*
{{3.35409, 0.883529}, {1.02062, 1.02716}, {1.47535, 1.45068},
 {0., 1.40268}, {0.611681, 0.}, {2.16284, 0.836485},
 {0.570805, 0.719401}, {1.40896, 0.0658664}}
*)

It's clear that they are not stored in g, I think.

You can see them in the vertexLocations list. For example, the first 10 coordinates may look like thees:

In[5]:= vertexLocations[[1 ;; 10]]

Out[5]= {{1.10698, 1.50615}, {2.19579, 0.841207}, {1.25174, 
  0.799162}, {2.10738, 1.51831}, {1.96417, 1.04546}, {0.680264, 
  0.819208}, {1.21224, 0.478298}, {1.40553, 1.90238}, {2.05948, 
  0.993345}, {0.651144, 0.728469}}