Fire Emblem: Radiant Dawn or Trauma Center: Second Opinion. Fire Emblem probably takes the top spot, but then again I only rented Trauma Center and never got to try the hardest levels.

From the ones I've played, Fire Emblem: Radiant Dawn, Trauma Center isn't too far behind though too, Halo 3 on legendary is also very hard.
From downloadable games, possibly Mega Man 9.

Am I the only one who found trauma centre easy?

did you play on easy?

I actually had to play on easy on a few of the later stages to progress the story. I didn't want to waste all my rental time on the same stage.

Demon's Souls.

If reviews are correct I will be adding Resonance of Fate to that list as well as Last Remnant when I get around to playing it.

NGS 2.

The game itself isn't so bad, but those team missions on ultimate ninja....impossible.

Mega Man 9, then Demon's Souls

Bayonetta. I dont have any experience of hack n slash games, so I wasn't really up on it. Played it on Normal mode and struggled through it (though I enjoyed it), and finally gave up on the last boss, far too much hassle. It just gets ridiculous. Then I thought GOW3 would be the same, chose 'easy' and almost fell asleep due to the lack of difficulty.

Fire Emblem: Shadow Dragon on Insane or Higher.

Yes, I always play games on easy first.