I'll divide my recommendations up:
Fiction
Ellis Peters: the
Cadfael series
Twee murder mysteries in mid-12th century England.
Ken Follett:
The Pillars of the Earth
The lives and times of people trying to build a cathedral in mid-12th century England. Part soap-opera, part architectural treatise, all "good read".
George Shipway:
Knight in Anarchy
Brutal account of one squire's baptism of fire into knighthood at the time of the 12th century Anarchy. Excellent on combat, arms and armour descriptions -- but not for those with a weak stomach.
Katherine Kerr: The
Deverry series
Excellent fantasy series that builds from low magic beginnings to very high fantasy indeed.
JRR Tolkein:
The Lord of the Rings
Nuff said, really.
Non-fiction
Robert Bartlett:
England under the Norman and Angevin Kings
If you only get one history book, this is the one to have. It covers just about everything. Absolutely superb -- I never travel anywhere without it.
Geis & Geis:
Life in a Medieval Village
Flawed, but very readable.
DM Stenton:
English Society in the Early Middle Ages
Inexpensive, novel-sized paperback. Very readable and informative -- perfect for reading on the train.
Ronald B Tobias:
Twenty Master Plots and How to Build Them
Eventually we all run out of ideas. This is possibly the most RPG-relevant of several creative writing books I have on the bookshelf.
Films and TV
Robin of Sherwood: superb British-made TV series from the early-80s. Atmospheric, moody, fake Celtic mysticism. I always think of Robin of Sherwood when I imagine Harn. And it's now available on DVD.
Robin Hood The little-known Patrick Bergin movie, made at the same time as Costner's abomination, and far, far better.
Braveheart Its history sucked, but it's a good story -- and it's surprisingly good on a lot of the little details of clothing, weapons, animals and the like.
The 13th Warrior Surprisingly good Vikings vs neanderthals romp. It's worth reading
Eaters of the Dead, the Crichton book it was based on, as well.
And, of course...
The Fellowship of the Ring and
The Two Towers.