If you enjoyed Final Fantasy XII, I think you would like Vagrant Story. The protagonist does fall into the "crazy hair" category, but otherwise the characters are more Shakespeare than anime (there's literally two characters called Rosencrantz and Guildenstern). It's set in the same pseudo-medieval universe of Ivalice, so you'll get the same serious tone and generally drab color palette. The story involves a fair amount of religious/political intrigue I think you would appreciate. The battle system is skill-based and mildly addicting, and the equipment-crafting system is integral to your success in combat, as opposed to being an afterthought. The soundtrack can get on the ambient side sometimes, but it's widely regarded as one of Hitoshi Sakimoto's best.
The only downside is that it was released for the original PlayStation, so the graphics might be a little painful. If you play it on your PS3, texture smoothing should help a lot. If you play it on your PSP, it should look about as good as other PSP games.