Interesting that Sakaguchi was on Iwada asks recently and mentioned that his games start with story first. But I think that's something that RPGs can get away with by their very nature.
It's not surprising to hear a Japanese developer say that, but one probably has to understand a caveat about it: Japanese developers have a history with constructing elaborate story worlds in games that don't have a line of dialog. I think this is in part because of their love of character design.
Eastern game makers have long applied the same standards for character design originating with manga and anime, in terms of elaborate histories, motivations, and personal traits.
Mega Man, for example, is a game with a lot of story that shows but doesn't tell. Dr. Light and Wily have a history together, Rock (Megaman) and Roll have traits, personalities, purposes, and histories. Boss robots have specific personalities and reasons for existing, and you can construct a story about them based on the level that they're in charge of.
There's no text (mostly) in the games themselves, but the story plays out and creates a memorable universe.
I think part of the conflict over "should games have stories" arises from very different views on what the story part of a game is. This generation we have a common stereotype of "games trying to be movies", arguably from western developers keen to use their game to compete with hollywood. They have a seemingly singular goal, and that's to become filmmakers competing with the traditional definition of film. Just with some interactivity grafted on.
But there are many ways for "story" to be integrated into a game, including ways that may have been invisible to gamers in the past, and so some take it for granted that "games didn't use to need stories, and they don't need them now".
So if we are to make games without a story. We make games about or for what?
When you explain to someone that you have this game. Its a shooter. They ask "Whats it like or about" you say. Well there is no story or anything you just shoot. Without a sense of story you lack the purpose for the actual character that your playing. What motivation do you get when you dont have a story?
This is the secret art of showing without telling that was a given in games from earlier generations. People think that a lot of old classic game archetypes "have no story, and didn't need them" but that's not true. A modern game like Left 4 Dead is considered a prime example of how to "show without telling", to let the world and the action of playing the game tell the story. Well, that's the way it's always been with compelling games. Even if there's not a lick of dialog on screen or in speech, a story can be constructed that justifies the game's primary goal.
A good, basic case in point, might be the Orbitron, the Xbox indie title. It's a "random" shooter, but thought was put into it with regards to the craft of the player and its pilot having an insinuated history, and the space station you protect being a real place. The inspiration was in part taken from the Wipeout series, which also crafted a universe and actors with purpose thanks to its fictional companies and race sponsors.
