Ahem. Eternal Sonata. I talk about this game too much, but it's deserving. Fantastic music, scenery porn, a well established plot, and a very nice combat system. Not to mention the fact that the main character is Frederic Chopin and he uses a conductor's baton to kick major ass in battle. Go buy it. Or rent it. Or act like a non-landlubber and download it( not that I'm for that though.) Just play it.
Also, I really enjoyed Sonic Heroes. The different character's paths through the game was nice, but level design blowed.