To their credit, there is plenty of terrific storytelling happening in Bethesda's games. In the lore, in-game books and notes, and as the Howard put it, "environmental storytelling". The only major gaffes I've seen in their writing are the game to lore inconsistencies within Oblivion, and scenarios in Fallout 3 that are a little hard to believe; obviously that's not counting the changes in faction characterizations and tone from the older Fallouts that people are still bitter about.
What I'd like to see in an open-world main plot:
- Nonlinearity: significant events that have to happen for the narrative, but not necessarily in any given order. But the order these events happen changes the scenarios behind other events. A laughably basic example of this is Mega Man X, where completing one stage would have an effect on a few others (Flame Mammoth's level freezing over, or Storm Eagle's airship crashing into Spark Mandrill's power plant).
- Great characters: Don Quixote isn't considered the greatest novel of all time for having a grand over-arching narrative (hell, most of it honestly plays out like an open-world game made up of side-quests), but for having great characters and using them to explore certain universal themes. (Well, and for arguably inventing character development and several archetypes still in use today. And the humorous attacks on pretentiousness, which are still relevant today. Man, I just love that book so much you guys, I'm sorry for going on like this.) Anyway, New Vegas did this really well with all of the companions, but it can be hard to do consistently in an open-world game where so many NPCs are more or less transient.
- A fluid/dynamic world: Maybe it's more of an ideal, since no one ever seems satisfied when games attempt it, but you know. A world that changes as we progress through the narrative; this is one of the areas where Fallout 3's plot is actually really successful, with how the Enclave starts appearing and spreading propaganda throughout the wasteland, and then again with Broken Steel. The overall tone of the game shifted in each of these situations, and it was awesome. Now, this also means that our own choices should have an effect on how the world changes, which is where Fallout 3 wavers.
Now, what I don't want:
- A main quest filled with "before I help you, please do this completely unrelated favor". I could call out New Vegas's main quest for this, but a better example would be almost every part of Morrowind's (or even Daggerfall's) main quest. It's an okay and believable plot device (or maybe I've just played so many video games that I don't care any more, it's so ubiquitous), since it introduces you to interesting new scenarios and familiarizes you with the setting, but it just doesn't feel like good narrative. What does fetching a Dwemer Puzzle Cube have to do with vanquishing Dagoth Ur, what does helping a bunch of Ghouls go to space have to do with the fate of New Vegas, etc.
- Urgency. All of Bethesda's main quests since Oblivion have had this sense of, wait why are you doing this little side-quest while the world is in grave danger?
- Getting locked out of significant amounts of content. In New Vegas, I believe and accept the situations where my faction affiliation or quest decisions lock me out of entire questlines and companions; I don't have a problem with it at all. But for an open-world game, I'd rather Bethesda avoid scenarios where that's the only logical outcome. This would limit their storytelling ability, yes, but there are still plenty of ways to handle this in an open-world fashion that could be just as good in terms of narrative quality. This doesn't mean I want every possible choice, path, and outcome available no matter who our character is; just that any character should be able to complete every quest somehow and reap some kind of reward for it. How they complete that quest and what they get from it is another story. I think this is the crux of what Todd Howard was getting at when he was talking about the story.