The positioning of the Legend has to be done like any other node (I used rank=sink to get it to the bottom) - you may play with its margin attribute for fine-tuning the position.
Edit:
Without using labels, that may be the direction to go for - I'm not sure whether it is to completely eliminate ranksep.
But on reflection, seeing the difficulty I'm having to position the legend alongside the main graph, the way the position of node rankings in the main graph affects those in the legend, and the complication in the source that this introduces, I'm tempted to try a different approach (see my other answer, use a separate graph for the key)
Lots of these anwers show nice ways to render a legend, and that's useful, but a major unaddressed problem is integration of that legend in the same output as the main graph. This causes all sorts of problems because things like rankdir and rank positions "leak" between the main diagram and the legend, making it hard to improve one without breaking the other.
After trying several ways of embedding a key within the main GraphViz image, I've decided that for me, it makes more sense to simply put the legend into its own, separate dot file, render it as it's own, separate, image, and then display the images side-by-side in my documents/pages.
This has a few advantages:
The .dot source code is substantially simpler.
It's very easy to change the rankdir of the legend graph to display the nodes above one another, or side-by-side, to produce a key that either sits to the right of the main image, or below it.
No leaking of things like rank positions from the main graph into the legend.