All too often we assume that medieval man imagined rather staid monsters: dragons that looked like those in the Monster Manual, giants that were simply big humans, etc. Do a google image search for medieval depictions of monsters. Browse through the results. Medieval man populated his imagination with stuff that could have been created using a random generator of D&D monsters, or stuff that could be found in Weird Tales. I particularly like this guy:
You can also try googling for images of medieval marginalia, there is a lot of AHEM interesting imagery including a number of monstrous creatures. Some of these are familiar, but many of them might be interesting as monsters. I have written up a couple for use in my campaign.