neato uses distance embedding methods. The paper linked describes Sugiyama-style rank embeddings as implemented in dot. 1) They're incomparable. 2) the theory behind neato was published in 2004 (http://www.graphviz.org/Documentation/GKN04.pdf).

There are research groups (I'm thinking of Tim Dwyer's specifically) that are specifically trying to improve the situation. When you say "it's just a pile of incompatible heuristics", it sounds like you haven't taken the time to try and implement a better solution.

Graph drawing is the kind of thing that seems trivial, right until you try to work on it.

(disclaimer: I'm clearly biased here since I worked with the people who wrote graphviz.)