Some very easy-to-find medieval mysteries, which most people seem to enjoy, are the Brother Cadfael mysteries by Ellis Peters. They're set in England during the civil war between Stephen and Maud, around 1120 IIRC, and the main character/detective is a monk in an abbey near Shrewsbury near the Welsh border. Any library should have them, and you don't need to read them in any particular order I don't think. (The Catherine le Vendeur ones reward reading in order, though -- the long character arcs are much stronger.)