Q:

Why is embassy spelled with E but ambassador with A?

It seems both words are related to each other through French roots (ambassade, ambassadeur), both of which are spelled with an "A" in the front.
Why and when was the initial letter of "embassy" changed to "E"? Does this also occur in other words?

Edit:
Wiktionary gives the following etymologies for ambassador:

From Middle English ambassadore
  from Anglo-Norman ambassadeur, ambassateur
  from Old Italian ambassatore, ambassadore
  from Old Occitan ambaisador (“ambassador”)
  derivative of ambaissa (“service, mission, errand”)
  from Latin ambasiator
  from Gothic  (andbahti, “service, function”)
  from Proto-Germanic *ambahtiją (“service, office”)
  derivative of Proto-Germanic **ambahtaz* (“servant”)
  from Gaulish ambaxtos ("servant"; also the source of Latin ambactus (“vassal, servant, dependent”))
  from Proto-Celtic *ambaxtos (“servant”)
  from Proto-Indo-European *h₂mbʰi-h₂eǵ- (“drive around”)
  from *h₂mbʰi- (“around”) + *h₂eǵ- (“to drive”).

and for embassy:

Modern variant of obsolete ambassy
  from Middle French ambassee (“mission, embassy”)
  from Old French ambascee (also enbassee (“message for a high official, official mission”))
  from Old Italian ambasciata
  from Old Occitan ambaissada (“embassy”)
  derived from ambaissa (“message”)
  from Late Latin ambactia (“service rendered”) (attested also as Latin ambascia)
  from Proto-Germanic *ambahtiją (“service”), ambahtaz (“follower, servant”)
  from Gaulish *ambactos* (“dependant, vassal”, literally “one who is sent around”)
  from Proto-Celtic *ambaxtos (“servant”)
  from Proto-Indo-European *h₂mbʰi-h₂eǵ- (“drive around”)
  from *h₂mbʰi- (“around”) + *h₂eǵ- (“to drive”);  
compare Latin ambactus, Old Irish amos, amsach (“mercenary, servant”), Welsh amaeth (“tenant farm”)).

It is noticeable that all these predecessors start with an "A" sound, only the latest change introduces an "E".
Here is also clearly mentioned that embassy is a modern spelling, but it does not explain when or why this change occurred or if similar words have undergone the same change.

A:

In French, "amb-" and "emb-" sound the same
In French,  <am> and <em> in this kind of context came to represent the same sound (some kind of open nasal vowel; the corresponding modern French phoneme is typically transcribed as /ɑ̃/). Because of this "merger", by the sixteenth century we see variation between <am> and <em> (or <an> and <en>) in the spelling of many French words, without regard for the etymological origins of the vowel.
Later on, French spelling became much more fixed and substantially more regularized, so related pairs of words like this usually are spelled consistently with <e> or <a> in present-day French (and the modern spelling often follows the etymology—I don't know whether there are any exceptions). But embassy and ambassador entered English during a time period when French spelling was still variable (similarly, English retains the digraph <oi> in the word connoisseur even though the modern French spelling has been revised to become connaisseur).
Another pair of English words that apparently have been affected by the same phenomenon is example/exemplary. I wrote an answer going into more detail beneath the following question: Spelling of Exemplary versus that of Example
A source I found while researching that answer, The formation and evolution of the French nasal vowels, by Bernard L. Rochet (1976), contains the following quotes explaining how this situation developed in French:

in Old French – with the exception of Picard – eN and aN seem to have been in the process of merging; the extent of the merger varied according to the regions and probably also to the social classes of the speakers. This sociological conditioning of the evolution of eN does not receive any direct empirical support from Old French texts but is inferred from the situation described by the sixteenth century grammarians.

(p. 87)

The numerous orthographic variants found at that period [the 16th century] indicate that whatever distinctions, based on the opposition eN : aN, were still observed, they were only the remnants of a rapidly disappearing situation. Thus, Robert Estienne (1549) acknowledges the following alternations: "cravanter ou craventer," "ambassade et embassade", "tencer, voyez tanser", "panser ung malade. Voyer penser," etc.

(p. 96)

Evpok♦'s answer to a relevant question on French SE, "Why are “an” and “en” pronounced the same? Pourquoi « an » et « en » ont-ils la même prononciation ?", links to the blog post "la nasalization", by G. Pascault, which says that the change "ẽ̩m > ãm" occurred around the 11th-13th centuries (the blog post presents it as part of a general set of changes involving nasal vowels receiving a more open pronunciation, like õ̩n > õ̜n, ĩn > ẽn and ü̃n > œ̃n).
The spelling of the common prefix en-/em- might have been an influence
Something else that seems like it might be relevant to the use of e in the  spelling of embassy is that many French words (or English words from French) start with a prefix spelled <en>/<em>.
This prefix has a variant spelling <an>/<am> that is used  today  in only a few words (such as ambush, anoint, annoy), but that was used in the past in more words ( e.g. the word emperor has Middle English spelling variants starting with <amp> and <aump>).
The Oxford English Dictionary entry for this en- prefix indicates that a fair amount of interchange occurred between an- and en- spellings before they settled down into their current distributions:

In Middle English (as in Old French, Anglo-Norman an- ) en- , em- , frequently became an- , am- (as ambush v., anoint v. (Latin inunctum), annoy v.; anhaunse, anjoin, anvenime, where subsequently respelt en-; andetted, subsequently endetted, indebted). This an-, am-, like the native prefix an- prefix1 , was often reduced to a- : see appair v., aprise n. Conversely, the prefix a- of various origin was often changed into en-, as in embraid.

Although the first syllable of embassy is not etymologically derived from the prefix en-, its spelling might have been influenced by analogy with the spelling of words containing this prefix.
Of course, a weakness of this explanation is that it does nothing to account for the use of am- rather than em- in the currently standard spelling of the word ambassador.
The English pronunciation is presumably based on the spelling
I would guess that the use of the sound /ɛ/ (the vowel found in the word "dress") in the first syllable of the modern English pronunciation of embassy is based on the spelling.

A:

The why is pretty simple: phonetically, it sounds like it should start with an "e". Plus, when you have one word doing it, it tends to spread.
The initial "e" in "embassy" is seen as far back as Shakespeare:

Here comes in Embassaie, the French kinges daughter.
Love's Labour's Lost, 1598

As for other words written both ways, I think Johnson (1755) can answer that:

Our authors write almost indiscriminately embassador or ambassador, embassage or ambassage; yet there is scarce an example of ambassy, all concurring to write embassy.

The OED notes:

Of [the spelling variants of ambassador,] embassador, supported by embassy, was much more common than ambassador in 17–18th cent., and was still the common spelling in United States in 19th cent.

Obviously, not all these spellings survived. At this point in time, nobody uses "embassador" or "ambassage".
Another word with both forms is the archaic word embassade/ambassade.
Some of these words also had spellings starting with neither "e" nor "a". For example, "ambassador", which dates back to Middle English, was also spelled with an initial "y", "j", and "i" (not that there was really any difference between "i" and "j" at that point). It's also relevant to note that ambassador was spelled with an "e" very early, with Chaucer being the earliest citation for both the "a" and "e" spellings of the word:

Thambassiatours hem answerd for final.
Troylus & Criseyde, c1374

Stilbon, that was a wis embasitour
Pardoner's Tale, c1386

