Valkyrie Profile, if you can get it. Wasn't there a Grandia game for PS1 too? Legend of Dragoon is a good turn-based mideival game, although it's really super linear. Dragon Quest VII, if you can obtain that as well. That's all I can think of that fit your criteria anyway.