I was just going to defend Half-Life 2 and say it's amazing not for the story, but for the storytelling. Then I read makingmusic's post that quoted that Sean Riley character's response to the OP. Beat me to it. Great post too!
And while I haven't played Ico yet, I've played Out of This World several times, and that's Ico's biggest inspiration. I can't gush about Out of This World enough. It inspired games like Ico that allegedly "got it right" and games like Metal Gear Solid that are convoluted cutscene fests. It inspired everything. It has almost no story, but the way it's told.... damn, that's the stuff.
And no no no, games don't need stories. Movies and books and songs don't even need stories. Does anybody care about the story of "Thriller?" No. But they love how the story is told through horror cliches, funky basslines, zombie dance moves, and Vincent Price. Any of those on their own is just "pretty cool," but the way they're mixed into a story is "totally awesome." Citizen Kane isn't considered by so many to be the greatest film of all time due to the story. It's considered the best for its storytelling, starting with the ending, then the news report, and mostly for the contradicting flashbacks with different points of view. Same goes for games.












