It's hard to decide where to draw the lines of "fantasy", and more importantly where to draw the lines of "medieval". Star Wars is essentially space fantasy, and your own definition of fantasy seems pretty broad itself, but RPGs tend to be very Tolkienesque -- half the earlier ones were directly based on D&D, which knicked a lot of ideas.
I'd give a mention to Morrowind, though it's one you likely know. It's an Elder Scrolls game, but unlike the others takes place in the Dunmer homeland, which is a lot more alien. You've got the swords, the shields, the armour, and even spears, but the land's full of exotic creatures (this [http://img3.wikia.nocookie.net/__cb20141211235520/elderscrolls/images/2/23/Silt_Strider_by_mage_116.jpg] is the equivalent of Skyrim's horse-driven cart fast travel), Dunmer culture is fairly unique, and houses are being built out of mushroom and crap. Key roleplaying moments come from deciding whether you're more loyal to the Imperial side of things or the ancient traditions of the Dunmer, but on the whole your character rarely speaks and characterization is left to your mind. So, this may not be your kind of thing, it's not too un-medieval, and it's also really pretty antiquated and the early game is hell. Still, could be worth a look.
I trust the Bloodlines you mention playing is the Vampire one? A lot of people are recommending it, though if you've already played it moot point.
Jade Empire is a game that bridges BioWare's KotOR and Mass Effect, essentially. Silent protagonist, you pick between lines of dialogue, there's a morality meter with some more nuance than light-side/dark-side but ultimately tends to be between being a puppy-kicker or a saint. The gameplay itself is sort of like a beat-up, though you get a single companion to take with you and develop different "styles" or abilities. The setting's the main draw. It draws a lot on martial arts and takes place somewhere heavily inspired by ancient China, and plays with some of those ideas like your old master and early on your rival, as well as some overarching ideas like order and harmony.
My own avatar comes from Fallout: New Vegas, and this is where we push the ideas of fantasy. Fallout has a lot of fantastical elements, the robots, the supermutants, the ghouls, ridiculous retrofuture technology, and of course a radioactive wasteland filled with giant scorpions and all other nasties. Nonetheless, your character is a relatively normal person -- they survived a shot to the head and prove essentially a one-man army by the end of it, but that's games for you -- and the core conflict is between two relatively down-to-Earth factions, Caesar's Legion (an anti-technology nod to ancient Rome, though far more rigid and absolutely not multicultural) and the NCR (an attempted recreation of modern day democracy, moreorless, though there are more flaws with them than that might initially suggest). Two factions, however, are far more fantastical, with heavy use of robots with old-school '50s cartoon faces. It also stretches the meaning of "RPG". It has dialogue, speech checks, character creation, karma and faction reputation, a variety of skills, gear, sidequests, some perks you can get on level-ups, and these are all pretty important, but generally the gameplay often feels quite like a regular shooter (though you can run a melee build, or try to use stealth as well, and so on).
