I second Perdurabo suggestion....Martin's series is superb...Though I will say the man seems to be stuck in a rut; after the first 4 books came out like clockwork, the most recent is 3 or 4 years late now, with no publish date in site.
My personal suggestion, if you care for historical fiction at all, is to read Bernard Cornwell's Saxon Stories or Warlord Chronicles. The first is set during the height of the Viking invasions of 'England' when Alfred the Great has come to power, and (ultimately) begins to push back the Danes. The second series is a realistic treament of the Arthurian legend, set right after the Roman withdrawal from Briton, when the Saxons seem unstoppable, and the native Briton tribes can't seem to get along. No (real) magic in either book (Merlin is a Druid, and his magic tends to be circumstance and deception), and both are set against real characters and events. (The Arthurian books are a little more tenuous just because there is so little written information about that period, but the main characters, such as the protagonists Aelle and Cerdic, are believed to have lived.) Really, really good reads.
As far as your specific request for medieval fantasy... been a while, but the Elric stories (Michael Moorcock) are interesting, at least the first books before the Eternal Warrior starts appearing in other times and places - these books are definitely not 'bland', or 'more of the same'. In fact, they get to be pretty damn trippy in parts.
It's a bit low-brow, more for teenagers, but I enjoyed reading the Raymond Feist books when I was a kid. Nothing particularly mind blowing there, but the books he wrote with Janny Wurts from the perspective of the antagonists in the first few books stand out as really good.
Just my $0.02. But I have to say Perdurabo stole my thunder. The Ice and Fire books are the best fantasy books I have read in a long time, and I have long since quit reading this genre. Too much of the same old, same old. Martin's book are dark, gritty, and violent. I'll just warn you - Martin has no qualms about killing off your favorite, central to the story character at any point. There's none of this 'it's just a flesh wound - I'll be back' crap in these books.