The Name of the Rose, by Umberto Eco. Set in a monastery in Italy. The book is a little weird, but the library is great, and Eco is a medievalist by training.

In high school, I also read most of the series of Kristin Lavransdatter, which is set in the 14th century in Norway. Beautiful writing, and very gentle.

I know this is weird, but you might also like reading some actual medieval literature. Some suggestions:

The Canterbury Tales will give you a real sense of local color in England in the 13th century, and will also show you a fantastic cross-section of medieval English society. (FYI, it's in Middle English, which, when read aloud sounds like English with a thick German accent. It takes some time to get used to it, but it's definitely readable. Get an edition that's annotated, so you can get definitions/explanations for some of the weirder stuff.)

I would also pick up Seamus Heaney's translation of Beowulf. What a fantastic epic. Heaney really preserves the pacing and epic tone of the original Anglo-Saxon. And how can you not like a story about a monster?

For more swashbuckling medieval lit, I would look at The Song of Roland, a very famous french chanson de geste. You can usually pick this up cheap in translation in second-hand bookshops.

And for the requisite Arthurian stuff, I would read The Quest of the Holy Grail (this version). It follows Lancelot and Galahad on their quest for the Holy Grail; written sometime in the 14th century in French, it's a classic, if a little bizarre (includes dream sequences, a large ship made from the timbers of Solomon's temple, etc.).

My Lord John by Georgette Heyer. Amazing research, great story teller. It is a biography, unlike her less serious but fun "Simon the Coldheart"

Some of Chelsea Quinn Yarbro's St Germain series are in the middle ages, eg Blood Roses. St Germain is a Vamp, and the parameters of that part of the stories are a bit irritating, but great research.

Year of Wonders by Geraldine Brooks.

Roberta Gellis did some great medieval bodice rippers, which I re-read recently and realised were great historical novels with a bit of bodice ripping thrown in for marketing purposes. Start with "Alinor"

Gellis has some more recently published mysteries which are full of historical info and atmosphere. Try "Bone of Contention" or "A Personal Devil"

Doomsday Book is so good! And I totally get what you mean about the slower pace, more in tune with nature’s cycles and such – you get that feeling from the Brother Cadfael books, I’d say.

Here’s a list of historical fiction set in the Middle Ages – it’s a few years old, but there are some good things on here.

Have you read Follett’s sequel to Pillars of the Earth: World Without End? If you’re ready to sink into another epic tale, this might seem to be just the thing.

Michael Eisner – not the Disney one – wrote a really great Medieval adventure called The Crusader, and then seems to have disappeared. Too bad, because it was very promising, and writes a good swift adventure. Which reminds me of Evan S. Connell’s Deus Lo Volt! – another book about the crusades by a really talented author, and clearly very well researched, though it is written in a somewhat archaic style that may not be to everyone’s liking. And stepping further into that, there’s always Umberto Eco’s astonishing The Name of the Rose. Eco does a really incredible job of luring the reader into this superstitious, elaborate, scholastic Medieval mindset, while stringing things together with a compelling suspense plot. Not exactly restful, but… Also Barry Unsworth’s Morality Play, which has something of a mystery and a great atmosphere that makes you feel like you’ve been plunked down in the middle of a Breugel painting, plus the intriguing backdrop of Medieval theater.

I also really liked Frederick Buechner’s Godric, a much smaller scale story by a writer who writes what I kind of wince to call “Christian Fiction,” because he isn’t doctrinaire or evangelical about it, and it really works well given the era he covers in this book. St. Godric was a hermit saint.

Then there are those bleak, bleak, BLEAK novels about Medieval Greenland – Jane Smiley’s The Greenlanders and Judith Lindbergh’s The Thrall’s Tale. Both books take you to the end of the world, this haunting lost world on the frontiers of Viking civilization, and both are very well done.

Dorothy Dunnett’s King Hereafter is a really enjoyable tale of the early Middle Ages, with a fanciful reconstruction of the historical Macbeth (conflated with the much better known historical figure of Thorfinn, Earl of Orkney). Very well researched, and full of great political machinations and stuff. Dunnett is better known for her two series – the Lymond Chronicles and The House of Niccolo – but this stand-alone is a great introduction to what she does.

Another very detailed chronicler of the Middle Ages is the French writer Zoe Oldenbourg – The World Is Not Enough is the start, followed by The Cornerstone.

Wow, everyone here has great recommendations. The only thing I would add, and it's a TOUCH fantasy but not too much, is "The Mists of Avalon" by Marion Zimmer Bradley. An amazing account of the entire Arthurian saga from a woman's perspective, and extraordinarily well done.

Her other books are good too, but veer away from anything done under her name by Diana L. Paxton.

I just wanted to add to all the people saying Name of the Rose. And also to say that Umberto Eco's other book set in the Middle Ages that I've read, Baudolino, is also fantastic. It may not be as "involved" as Name of the Rose, but is full of little details about Medieval Europeans' views about the lands they didn't know about - y'know the places where cyclopes, bird-women, unicorns and headless one-footed men live... An excellent and very fun read. (Foucault's Pendulum - not so much).

Italo Calvino's Invisible Cities is not really a book that's in any way about the middle ages, but it is, at least technically, set there, and is totally great (His other medieval stuff - not so much).

Dario Fo wrote a very thought-provoking, in my opinion, piece (officially a play, I guess?) about the Middle Ages called Mistero Buffo. More about Popes than you probably wanted to know! It's like half a day's reading, so it's all-encompassingly* worth your time.

Also, Rabelais' Gargantua and Pantagruel. It has this reputation of being impossible to read, so I was greatly surprised at how readable and funny it was. This isn't to say I anywhere near finished it or anything, but still... Gargantua is hilarious. And very medieval!

Not fiction and might totally not be your thing, but I was recently reading a book about the Bayeux Tapestry called "A Needle in the Right Hand of God" that was unexpectedly awesome and have been itching to recommend it to somebody somewhere, so there. It is very good at portraying some of the medieval mindset...

*I noticed I was using totally too much...