I found all this fascinating because I think that Colossus is a model for how narrative ought to be done. The capacity to convey narrative through interaction is a constitutive rather than accidental feature of the medium. Every time a designer exploits this ability we get closer to finding out what kind of art games are, and what forms of expression are unique to games in comparison to other media.
All this talk about Colossus also inspired me to write about boss battles, because I believe that the game is the culmination of an interesting design heritage. Boss battles were first thought up in the arcades: at the end of a level (or segment of the level) you would run into an enemy that was just bigger and stronger than the rest of the enemies you faced. The boss could take more damage, had more damaging and harder-to-avoid attacks, and so forth. My dominant memory of boss battles during this era was that they were expensive. (I remember that you always had to have a row of quarters ready when you started to fight Krang.)
The first game I remember ever fundamentally altering this formula was the original Legend of Zelda for the NES. At the end of the second dungeon, you were faced with a Dodongo, an enemy that differed from all your previous enemies in kind rather than just in degree. The rhino-looking bosses could not be defeated by normal sword slashes; rather you had to get him to swallow your bombs by laying them out in front of him. You had to figure this out on your own by experimenting with your various items.
This fight, simple on its own, is the seed of two great design ideas, both of which have been developed to an impressive degree of maturity. The first idea is using boss fights to test the player's knowledge of the existing game mechanics and to teach her to apply them in new ways. (You can think of the Dodongo fight as the discovery of a new “rule” for the use of bombs.) In the later installments of the Zelda series, each dungeon would have a series of puzzles and obstacles organized around the use of an item found in that dungeon. And then the boss would be a sort of “final exam” to test your mastery of the new rule the game taught you in the dungeon: you had to use the techniques you've used throughout the dungeon in novel or more complicated ways in order to damage the boss. This template was perfected Legend of Zelda: The Ocarina of Time and descends into mannerism in Phantom Hourglass. This approach to boss battles has been a hallmark of the Metroid Prime series, and Okami used this idea to great effect by applying the principle to many of the game's non-boss enemies.
The second design idea nascent in the Zelda fight was making boss battles into puzzles. Beating bosses became not just a matter of moving faster and inflicting more damage, but fundamentally a matter of problem-solving. Just managing to inflict any damage at all became the central challenge of the fights. In the Zelda games you had to keep an eye on your environment and the boss' behavior in order to discover the trick to beating the bosses those games threw at you. Reasoning this solution out produces these “aha” moments-- moments where you recognize the designer's mind at work-- that are Zelda's great gifts to gaming.
I see Colossus as the consummation of this latter stream of evolution. Shadow of the Colossus introduces a minimalist set of game mechanics: riding, shooting arrows, climbing, stabbing. It eliminates all the levels and battles with regular enemies, and substitutes the exploration of a large and mostly featureless world. (This game has extremely slack pacing; it contains some long stretches of eventlessness that would make Andrei Tartovsky proud.) And finally, it constructs a set of meticulously designed environmental puzzles in each colossus encounter. These innovative design choices (along with its beautiful visual style and its subtle approach to narrative) make Colossus a unique experience, even though its basic gameplay ideas are part of a long tradition. It exemplifies a pattern that is true of other works of art: it draws upon the established forms of its forebears and transfigures them into something noone has ever seen before.