Here are 20 names for girls and for boys which were unexpectedly common during the Middle Ages.
My main source for these names comes from George Redmond's Christian Names in Local and Family History in which he ranks 1000 names from ten counties in the poll taxes between 1377 and 1381.
Julian
The Latin Julianus and Juliana both became Julian in vernacular Middle English. So, just like Philip was a name for both boys and girls in the Middle Ages, so too was Julian.
Julian, however, managed to race ahead in usage for girls thanks to Saint Julian of Norwich (1342-1416), an anchoress and theologian.
The female Julian was also found as Gillian, perhaps to distinguish it from the masculine form.
In Edmond's ranking, Julian was #11 for women in the 1377-81 poll taxes.
Amice
Amice was the vernacular form of the Latin Amicia, most likely derived from the Latin amicus "friend." A saint Amicia was venerated in Brittany which may explain some of its popularity.
In Edmond's ranking, Amice was #16 for women in the 1377-81 poll taxes.
Sybil
In Ancient Greece and Rome, sibyls were female prophets who were thought to possess divine foresight. In the Middle Ages, the name was spelled Sibyl or Sibley and even developed the diminutives Sibb and Sibot.
In Edmond's ranking, Sybil was #21 for women in the 1377-81 poll taxes.
Felice
Felice and Felis were the vernacular forms of the Late Roman name Felicia, derived from the Latin felix "lucky, fortunate."
Felice was the lady love of Guy of Warwick, the legendary hero of English and French chivalric Romance. There was also a third century saint with the name.
Felice later became much confused with Phyllis.
In Edmond's ranking, Felice was joint #22 for women in the 1377-81 poll taxes.
Christian
Like Julian, Christian was another unisex medieval name that was more common for girls. Both Christianus and Christiana can be found in the Latin records, but both had the vernacular form of Christian.
In Edmond's ranking, Christian was joint #22 for women in the 1377-81 poll taxes.
Avice
Avice was introduced to Britain by the Normans from the older Germanic name Aveza. It's origins aren't clear, but it could be derived from Ava, or as a form of Hawis (from Hadewidis "battle + wide"). It could also be derived from the Latin Avitia "ancestral" via the Roman family name Avitus.
During the Middle Ages, Avice became associated with the Latin avis "bird," and eventually the spelling Avis became the usual form.
In Edmond's ranking, Avis was #23 for women in the 1377-81 poll taxes.
Isolde
Most likely thanks to the popular Romance of Tristan and Isolde, Isolde was quite popular for girls in the Middle Ages, though most likely girls by the name were called Isot or Isaut in everyday.
In Edmond's ranking, Isolde was #26 for women in the 1377-81 poll taxes.
Petronille
Petronilla was the name of a 1st century Roman martyr and considered to be the feminine form of Peter. Queen Eleanor of Aquitaine's sister Alix was known as Petronilla during her childhood.
Eventually, the vernacular form Pernell / Parnell developed. However, this vernacular form later came to be used to refer to a priest's concubine, which may explain why it declined in use by the 17th century.
In Edmond's ranking, Petronille was #28 for women in the 1377-81 poll taxes.
Lettice
The vernacular form of Leticia (Latin laetitia "joy, happiness") which was also found in the Old French form Lece. In some cases, the diminutive form Lecelina lead to the surname Lesley.
The traditional English pronunciation of Lettice is LET-iss much like 'lettuce'.
In Edmond's ranking, Lettice was #32 for women in the 1377-81 poll taxes.
Idony
Derived from a Norse goddess of Spring, Idony was quite common in the Middle Ages. It was Latinised as Idonia or Idonea, the latter of which matches the Latin idoneus meaning "suitable."
Lady Idonia de Clifford was the daughter of Robert de Clifford, 1st Baron de Clifford (1274-1314), 1st Lord Warden of the Marches, responsible for defending the English border with Scotland. Her granddaughter, Lady Idoine Neville, was the great aunt of Edward IV and Richard III.
In Edmond's ranking, Idony was #35 for women in the 1377-81 poll taxes.
Benedict
Saintly and popely Benedict was well used in the Middle Ages and led to the vernacular form Benet.
The feminine Benedicta also became Benet, which means both boys and girls answered to the name. It was, however, more commonly used for boys.
In Edmond's ranking, Benedict was #31 for men in the 1377-81 poll taxes.
Jena
In the poll taxes, we find the mysterious occurrence of Jena for men. Jen and Jan were short forms of Jehan, the Old French form of Johannes (John), so it's most likely that Jena represents this.
In Edmond's ranking, Jena was joint #40 for men in the 1377-81 poll taxes.
Madok / Eyvyn / Griffin
Madok, Eyvyn and Griffin were not uncommon in the Middle Ages in the Welsh-English borders. They were all anglicised forms of the common Welsh names Madoc (Madog), Evan (Ieuan) and Griffith (Gruffudd) which were used in Welsh nobility.
In Edmond's ranking, Madok, Eyvyn and Griffin were joint #43 for men in the 1377-81 poll taxes.
Maurice
Saint Maurice was a 3rd-century Roman soldier who became a patron saint of infantry soldiers. His cult was a popular one in the Middle Ages.
The name was brought over to Britain by the Nomans and became commonly spelled Morris.
In Edmond's ranking, Maurice was joint #43 for men in the 1377-81 poll taxes.
Hamond
Hamond and Hamon were the English forms of the Germanic names Haimo "home" and Haimund "home + protection."
Shakespeare used one of the diminutive forms, Hamnet, for his son, and another, Hamlet, for the titular character of his famous play.
In Edmond's ranking, Hamond was joint #43 for men in the 1377-81 poll taxes.
Stacey
Stacey, or Stacy, was the diminutive form of Stace, itself the medieval English vernacular form of Eustace. Saint Eustace was a 2nd-century Roman martyr whose cult was popular in the Middle Ages.
In Edmond's ranking, Stacey was joint #43 for men in the 1377-81 poll taxes.