Quibbling about Gemmell’s originality aside, the OP asked for fantasy with “fictional kingdoms, evil kings, lady warriors, wise old mentors” and “sword play, kings and barbarians, etc”. Gemmel’s books fit that bill. 
Coming back to your criticism, I’m very happy to categorize (most) of Gemmell as pulp-fantasy, an updated Howard-esque writer… the McDonalds of fantasy writing even… I did however very much enjoy his recent (and last) series set around the Trojan war.
T. H. White’s The Once and Future King might serve. The first book, The Sword in the Stone is full of Merlin and magic, but after that there’s no magic at all in the retelling of the story of Arthur.
Lloyd Alexander… ummm… it’ll come to me… Westmark. No magic.
I read Mimus recently. You might like that.
Just out of curiosity, has this ever been an issue with Bujold’s work? Are people actually accusing her of pedophilia because two teenaged nobles get married in a medieval fantasy setting?
I confess I haven’t read those. I’ll give 'em a shot if I come across them.
I’m a big fan of Gemmell, but won’t argue at all that his plots are cliche. For me they are a light fun read - but yes, cliche.
You might try Lion Of Ireland. There was the tiniest bit of magic in it, but really, not much.
The Last Light of the Sun has some supernatural/ghost like elements to it, as well as some ability related to premonition in one character. I do think that the worlds created in Guy Gavriel Kay’s books would fit what the OP is looking for quite nicely, and I second the suggestion of The Lions of Al-Rassan. *Tigana *was quite political as well, although there was also some magic in the book.
Would the Princess Bride count? I don’t really remember if Billy Crystal’s character was truly magical, or just a chemist of some sorts. I don’t remember anything else that would constitute magic.
A Song for Arbonne *and the Sarantine Mosaic (along with Al-Rassan) are definitely what the OP is looking for. They’re all set in close analogs of actual historical periods - the Albigensian Crusade, Byzantium at the time of Justinian and the Reconquista, respectively - and while magic exists, it’s vanishingly rare and basically peripheral to the story.
Tigana, while also historical-based (Renaissance Italy), has quite a bit more magic, and the Fionavar Tapestry… well, lets just say that all of the standard fantasy elements absent from the rest of Kay’s stories are very, very present there. And then some.
The Ingenious Hidalgo Don Quixote of La Mancha. Full stop. Everything you’re looking for and so, so much more. Get a version with annotations–there are a lot of puns and wordplay in it, and a lot of references. It will have you in stitches from the moment he tests his helmet to the last reference to that “false” Don Quixote. It will take you to the heights of glory and the depths of despair without ever offending your sense of proportion. There are giants, monsters, and the very fabric of fantasy ahead of you yet there is no questioning of your sensibilities.
Maia and Shardik by Richard Adams.
Mary Stewart’s Merlin books straddle the line between historical fiction and fantasy.
It hit me last night that Princess Bride is actually exactly what I’m looking for. The ROUSs are the closest thing to a monster and Miracle Max does seem more like a carzy chemist/herbalist.
It does seem that there’s not a lot in this sub-genre. I think most of the suggestions here have said “there’s a little bit of magic but”
Thanks everyone.
Along with the killer eels, machine that drains life and the holocaust cloak, I’d characterize it as low magic and monsters, but not zero of either.
True. Don’t take that to mean (from me at least) that we’re trying to persuade you that a little bit of magic is what you need, rather trying to judge / refine your requirements. Some people might say “no magic” and mean no wizards with fireballs but think some prophecy was OK, etc… basically that they don’t want the sort of fantasy where magic is used to Deus Ex out of difficult plots elements, but is alright if incidental to the main storyline… that sort of thing.
I came in here to suggest the Black Company novels, but Kobal2 beat me to the punch. There’s magic, but it’s not a panacea/ all-purpose plot device like it is in most fantasy novels. The people who use magic are varying degrees of terrifying psychopaths. The story is really about how this group of mercenaries lives day to day, albeit in interesting times.
I would also suggest you check out K.J. Parker’s Scavenger Trilogy. Again, there is some magic, but mostly in the form of dreams and strange happenings. Mostly it’s just gritty Dark Age surrealism.
I win the thread!
In addition to Glen Cook’s Black Company novels (his best), you can also check out his Dread Empire series, which has magic, but the plot relies on it a lot less. The first book is the most magicky. In the rest of the books, the lead characters have almost no magic on their side, and win or lose mostly by sheer might of arms. Has a Mercenaries Guild which runs heavy infantry and heavy cavalry in tightly drilled formations, a Mohammed-like religious war among horse-bandit desert nomads, a Bushido-style crack East Asian army, and a city of scholars and finance that sounds like a cross between Athens and ancient Judea.
It’s a great series, but it’s about a centuries long war between immortal/undead wizards, and a prophecy about a reincarnated savior who will finally end it. I’m hard pressed to think of many novels that are less like what the OP is looking for.
I recently read the KJ Parker Engineer Trilogy, which despite its name is exactly what the OP describes - medieval nobility fantasy-like setting (just on the brink of industrializing) but absolutely no magic, no psionics, nothing supernatural – I was actually really surprised to realize this halfway through because the setting is so very common-fantasy-like. However, warning that it is incredibly depressing, although I thought it was very good. I wonder if things in this genre tend to be really depressing?
Honestly, though I adore Bujold like anything, and Curse of Chalion is one of my favorite books, Curse of Chalion and (much more so) Sharing Knife kind of annoy me because a much older man gets married to a girl just out of adolescence. Curse of Chalion isn’t so bad, because the man is (IIRC) in his 30’s, the woman has weathered enough fairly substantial political crises that she’s pretty much grown up, and they’re both nobility where these kinds of matches are common. Sharing Knife, however: the man is something like 100 years old (literally… he comes from a long-lived people) and the girl is a teenager. He’s been married (and widowed) before. That is a HUGE ick factor for me that really interferes with my enjoyment of the SK books.
I wouldn’t call it pedophilia, though, just icky.
Missed the edit window - did you mean the two royals, who are both 16 or so? Yeah, that’s totally fine, anyone who has a problem with that is nuts.
Fifty five, actually. Still a hell of an age difference, but nothing at all like a hundred years.