Some examples of legend positioning in R lattice. There is nearly infinite flexibility if there is strong desire for customization. This illustrates some of the options available.
A lot of times I like to avoid legends entirely and use the direct.labels package to label the graphics directly.