You know what it means to be at loggerheads, but do you know what a loggerhead is? According to the Oxford English Dictionary, a logger is a "heavy block of wood fastened to the leg of a horse to prevent it straying." Combined with "head," it becomes a synonym for blockhead. The first usage recorded is in Love's Labours Lost:
"Ah you whoreson logger~head, you were borne to doe me shame."
The term is also applied to animals whose heads are too large for their bodies, like loggerhead turtles. But to be at loggerheads is another matter altogether.
There is considerable disagreement about the origin of the phrase, but I suspect that it comes from the tool known as the loggerhead. "an iron instrument with a long handle and a ball or bulb at the end used, when heated in the fire, for melting pitch and for heating liquids." (Metaphorically, it is an animal whose head is too large for its body.)
There is an instance in Patrick O'Brian's vastly entertaining maritime adventure, The Commodore, in which two Royal Navy sailors had playfully batted at each other with these unwieldy instruments and could be said to have suffered the effects of being truly "at loggerheads":
There were two invalids in the starboard sick-berth, whom Padeen had been sitting with. They had been sparring, in a spirit of fun, with loggerheads, those massy iron balls with long handles to be carried red-hot from the fire and plunged into buckets of tar or pitch so that the substance might be melted with no risk of flame. 'They are sober now, sir; and penitent, the creatures.'
This would likely be the nautical equivalent of running with scissors.
PS: Can anyone find a picture of a nautical loggerhead? All I can find are turtles, turtles, turtles.