I concur with what you said about Koudelka. Of course any game where the female lead doesn't have to be a mage and takes a back seat to the guy is okay in my book.

There's Septerra Core. A fun RPG with a unique cast and different battle system. I really liked the battle system, but I a lot of people didn't. They probably didn't get far enough to get new skills are magic cards to have fun with it.