Haeda is a strange one, I can find two different possibilities either from the Old Norse 'hæða' meaning "to mock" which seems a little unlikely or the Old English 'haeda' meaning "state" (haeda is the word that -hood, in words such as childhood, boyhood, is derived from).
Eidyn, as in Edinburgh, is of unknown etymology but it's suggested it may be a British form of the Irish goddess
Eithne (whose name is said to mean 'kernel, grain'.