I read the OP's spoiler notes about what he liked and what he didn't like. So my recommendation...
Jack Whyte's Camulod Chronicles or Bernard Cornwell's Warlord Chronicles. Both are serious attempts at retelling the Arthurian mythos in the historical context. Not a lot of magic, but serious worldbuilding and characterization.
Also, Harry Harrison and Tom Shippey's The Hammer and the Cross
, an alternate history of the Viking Age. I'm not as sold on the next two books in the trilogy, but I think the first is great.
Greg Cox wrote:
And there's always the Fafhrd and Grey Mouser series by Fritz Leiber.
Best. Fantasy. Ever.