Here’s one I forgot to mention in my last post: “In the Court of the Crimson King” by King Crimson.
If you’re in the mood for a little classic metal, there’s always Iron Maiden, with Rhyme of the Ancient Mariner… ?
S^G
(Video:) Emotional Rescue - Rolling Stones
I wanna be your knight in shining armour
Riding across the desert on a fine Arab charger…
Scarborough Fair- doesn’t mention knights and queens and dragons, but does have a medieval feel and refers to going to a medieval fair.
Kenny Rogers’ Lady (“I’m your knight in shining armor and I love you…”)
Tonight is What it Means to be Young from the movie Streets of Fire (angel in the forest- boy in a castle ‘dancing like a cat on the stairs’, etc.)
Most of Spamalot 
That kind of makes sense. A lot of Appalachian songs are adaptations of medieval (or slightly later) Scots, Welsh or English ballads; one of the roots of American country music.
A movie on that exact subject (very loosely inspired by a true story and with some creative input [no appearance by] Dolly Parton). It’s about a folklorist and music historian who is stunned to find the “missing verses” to songs she’s studied academically while visiting a friend who’s a missionary in Appalachia. (Conversation With Death, featured in that movie, will send chills up your spine when sung acapella by hillbillies and has its roots in a medeival morality play.)
Pulling Mussels (From the Shell) - Squeeze (Mostly a modern beach setting for this song, but it mentions Maid Marian and William Tell.)
Catapult - R.E.M.
Van Morrison, “Tupelo Honey,” has the lines “You can’t stop us on the road to freedom/ You can’t keep us 'cause our eyes can see/ Men with insight, men in granite/ Knights in armor bent on chivalry.” Awesome song, too.
Tori Amos’ “Song for Eric” (link is to a video of her singing it live) has that classical imagery, and it sounds medieval, performed a capella.
IIRC, Dave Pegg played for both Fairport Convention and the oddly overlooked band Jethro Tull. I’m kind of surprised no one has mentioned them, as the album “Songs From the Woods” is swimming in medieval imagery, as is part of Broadsword as well as some others. “Minstrel in the Gallery”, despite its name, is not.
Then there’s “Kings and Queens” by Aerosmith.
One Tin Soldier - The Original Caste (as featured in the Billy Jack soundtrack)
If You Could Read My Mind - Gordon Lightfoot:
In a castle dark
or a fortress strong
with chains upon my feet
And as for songs with a medieval vibe, there’s also
Lady Jane - The Rolling Stones
“Lucky Man” (Emerson, Lake & Palmer) conjures up medieval imagery for me.
Al Stewart, Merlin’s Time.
Give it a listen.
Since nobody’s mentioned it, might I add Jethro Tull’s album Songs from the Wood?
That album had Closer to the Heart, doesn’t it? Which is another song I thought of when reading the OP but forgot to include in my post.
I don’t know if it’s what you’re looking for, but Return To Forever’s *Romantic Warrior * seems intended to evoke medieval imagery.
Also, you might like some Camel especially “Nimrodel>The Procession>The White Rider” and “Lady Fantasy”.
Days of Love and Innocence
Thanks a lot everyone 
This thread has given me much iPod food and also soul food.
I’ve listened to about 5 of these and they’re exactly what I was looking for, will listen to more and post some comments.
Thanks again.
The entire cast recording of Blondel.
“Raconteur, troubadour” by Gentle Giant. Much of their catalog, in fact, contains gregorian harmonies, medieval instruments etc.
Let’s not forget Spinal Tap:
*Stonehenge! Where the demons dwell
Where the banshees live and they do live well
Stonehenge! Where a man’s a man
And the children dance to the Pipes of Pan
Hey!*