Not quite medieval but there are records of black people living in London since the 16th century (there are also records of black people living in Roman Britain). They seem to of made their way to Britain from Andalusia as their arrival occurred at the same time as Catherine of Aragon's marriage to Henry VIII and St Botolph parish in Aldgate describes these people as blackamoors in their records. More black people arrived in England later on in the 1600s as Spain was then at war with England and the Moors.
There were attempts and petitions to deport these blacks to Africa or even sell them into slavery in Lisbon but these were not successful (England and later Great Britain were more than happy to profit from the slave trade yet there were few slaves in the country itself, it was illegal for free men who had not committed an offence to be forced into indentured servitude and from 1722 and slave that set foot on British soil was deemed a free man). The black community in England further developed with the slave trade particularly in the main slave trade ports of Liverpool and Bristol made of black sailors, freed slaves and the children of traders (I think Liverpool's black community dates from the early 1600s).
Ad you expect there was discrimination but in terms of state rather personal discrimination, the country was more concerned with making sure catholics didn't get into any positions of power rather than attacking the black population.
on a somewhat related, though extremely unlikely hypothetical, what if ethiopian christians showed up?
hi! there have been similar questions; I've located few but I know I'm missing some. In any case, see these for previous responses
Were there any Black (African) knights in Medieval Europe?
Were there any black crusaders/templars?
How prevalent was racism in medieval Europe?
Did the Celtics have any contact with Africans?
Did black people have rights in England before the slave trade began?
edit: found some more!
Were there Arabs and Asians living in Western Europe during the Middle Ages/Early Modern Era?
How alien would the idea of a non-white person be to somebody living in medieval England?
What is your definition of 'person of color'? I'm personally not a fan of this term, as all it is is a contrived way of saying 'non-white', which is a very nebulous category itself. Are Persians people of color? What about Jews?
As for whether or not non-Europeans lived in Europe during the Middle Ages, it was not unheard of for darker-skinned people from the Middle East to live in Mediterranean port cities in Europe such as those in Italy or Greece. In fact, Sicily, Crete, and even much of Spain were all directly under Muslim rule at at least one point in history after they were conquered by invaders from North Africa and the Middle East.
While not impossible, a person from Sub-Saharan Africa (I'm assuming this is the group you're asking about) would have little reason or means to travel to Europe, as direct contact between the two regions didn't become commonplace until the Renaissance, and was mostly limited to trading even then.
Racism as we know it today is relatively new, at least in the Western world. Prejudice was frequently over culture (especially religion) rather than appearance. If a person from Mali were to go to Europe, Europeans would most likely dislike them not for being black, but for being a Muslim. An Ethiopian would likely be considered strange and foreign, but they would be more readily accepted due to being Christian.
I've found the BBC show History Cold Case very helpful in getting science majors interested in my history classes. It's like historical CSI. This was an episode on a medieval body found in Ipswich that turned out to be African. Apparently while rare, it was not entirely unheard of for Africans to travel north. This man could likely have been a cleric, which might have been his reason for travelling.