Neobr10: What about their previous game Discord Times?
http://aterdux.com/projects/discord-times/
Sadly more of a strategy game, as far as I can tell.
BlackMageJ: Would HP Lovecraft be fantasy-y enough?
Call of Cthulhu: The Wasted Lands seems to be a kind of X-Com/Jagged Alliance sort of thing with eldritch abominations. Haven't played it myself, but it's on my 'pick up one day when the Android version's on special offer' list.
http://store.indiecity.com/game/Wasted-Land Not quite. I know, I have a tricky itch to scratch right now, but the reason why I'm after a bright & colorful fantasy game is because I find them to be cozy and charming. While CoC: TWL is a good game (I've played it a bit, when I borrowed my sister's android pad), it is not quite what I'm after.
KillingMachine: It's not for PC, but you mentioned that you had a Wii that you wouldn't rule out. If you'd want to use the backwards compatibility on it, Gladius for the GameCube seems like it would fit your requirements. Here's a link for video review about it:
http://youtu.be/7DzZaOQWe9g That looks interesting! But why is it so expensive?! I'll have to keep my eyes out for it, in case it drops in price (with postage, it would cost me almost as much as a new game)
Stooner: Did you tried Might & Magic: Clash of Heroes, AFnord?
I was under the impression that that is basically a puzzle game with Might & Magic characters. Am I wrong?
FraterPerdurabo: I haven't played this game, but have you heard of Drakensang? From what I've heard about it, I'd imagine it might just tickle your fancy.
The two Drakensang games are straight up CRPGs, with Baldur's Gate-ish combat. Good, but not what I'm looking for (and getting River of Time is a pain in the rear for anyone not living in the US). RoT is the better of the two games).
lowyhong: Knights of the Chalice video. I think you'll like it.
Sadly I've already played that one as well. It made interesting use of the OGL (Open Game Licence, basically the D&D 3.5 ruleset)
Asmo2: FE is similiar game to MoM, FF Tactics, Tactics Ogre etc if you like fantasy tbs must try this game :D
I found a LP of it from the beta, and it does look quite interesting. But it is not out yet (well, apparently you can play the beta if you pre-order. Have you played it, and if so, is it in a playable state yet?