Shadow Hearts: Covenant is my suggestion, you don't need to have played the first one (Shadow Hearts) to enjoy it although that is also worth getting. Another PS2 suggestion is Xenosaga. These both have a lot of cut scens so only get them if you're okay with that. For PS1, xenogears is pretty good (very complicated storyline- lots of cut scenes) and I've been enjoying FFIV as I've played through it (FF chronicles for the ps), this is also comes with the absolutely wonderful game chrono trigger. The sequel chrono cross is my favorite non-ff ps1 game.

Shadow Hearts: Game with a good dark feel, perfectly good ps2 graphics, a reasonable storyline and pretty good characters. Uses the ring system in combat which requires good button pressing timing.

Shadow Hearts Covenant: Lighter feel with dark moments and hilarious scenes mixed perfectly. An excellent storyline with wonderful timing for when you learn what. I loved most of the characters and the voice acting was usually great (except a minor character in your party, Lucia... yuck). The graphics had a well done feel and were strong maybe on par with FFX. My favorite non-ff of all time. Uses a more in depth, more customizable, better ting system. It can be hard but I found it really fun, it's based on timed, quick button presses.

Xenosaga: Very long cut scenes but a very interesting storyline shown in them. The characters won't so strong but there were still ones I cared for. The graphics were a little bland but fine. Good battle system. The sequel wasn't as strong as the first game but I still enjoyed it a lot.

FFIV: Haven't gotten far yet, but I like the feel, the 5 character combat and Cecil, Tellah (only for one quote) and Kain.

Chrono Trigger: An excellent game that's feel excedes all. The characters were good with one great, Magus. The story was fun but I didn't find it special. The feel of this game is what makes it great.

Chrono Cross: The sequel to chrono trigger (which you must have played first to understand) has in my eyes the same feel and much better characters. The biggest improvement is one of the most wonderful storylines I've ever played through.

Hope these suggestions helped.