I'm going to second Alucard on MGS series as well as the MegaTen series as they are both absolutely beautiful and deep series that have destroyed my perception of what a game should be. Suikoden is another series with complex storytelling though its about politics so I hope thats not a turn off. Have you played FF Tactics or the Ogre Battle series?