I really like historical fiction with a fantasy style. My favorite author on that count is probably Steven Lawhead, who is currently doing a Robin Hood based (uh, sort of anyway) trillogy starting with
Hood. It's pretty good! I also adored his
Byzantium novel. No magic, lots of adventure.
I also just finished
Gentlemen of the Road by Michael Chabon. It reads just like a Fafard and the Grey Mouser story, but set on Earth and with no magic.
Sure, the worldbuilding of pure fantasy novels is great - but there are so many interesting cultures, places, and times on Earth... you can get just as lost in them and learn something as well. Authors who make their own worlds just have it easy - they can steal whatever they want from history, but don't have to do research.
As to Song of Ice and Fire - isn't it amazing how it reads like a low magic world? It does... but when you try to describe it, well... There are dragons. And zombies. And giants. Magical bonds with animals. Prophetic dreams. Even spellcasters of various sorts and powers. And yet, it feels far more like medieval europe than, say a D&D game ever could.