Breath of Fire: Dragon Quarter. It wasn't THE hardest game ever, but it's waaaay up on the list. But I love it, I'll still play it today if I ever get a new PS2. It was a beautiful game waaay ahead of its time, that Final Fantasy series is only now finally catching on to in quality. It's one of the few games where you WILL die at least once your first time through, no matter what you do, not by design, but by the mistakes that you're bound to make, since literally every step in the game you take added to your death countdown. But also, it was alot of fun and very creative. Even Dead Rising ripped off its continue system from it (since many of the same team members created both games).
Plus, it was the only game that made a friggin fun STOCK MARKET minigame that was addictive. Yes, like the Dow jones kind of stock market
Oh, and Shinobi was THE GAME!!! I love that game, and (almost as much) the sequal, Nightshade/Kunoichi