I liked Shadow Hearts, but it'd be next to impossible to find it now. I'd recommend you just start with the sequel, but that gives away one of the best plot twists in the game almost by its very nature. It's similar to Final Fantasy because a lot of the people who worked on it were originally from Square.

Hmm... Star Ocean 3 was really good.