With ODST, it could've done with being longer, I mean seriously, I don't see my dad very often, and we managed to get through ODST in a weekend (about 6 hours, I think). Can't remember the storyline for Reach, but I know that it's likely to be something that only fans of the series will understand/appreciate.
Skyrim has a storyline? All I've been doing is fighting dragons and stealing things. Can't judge because I haven't finished.
With Pokemon, I don't really judge it on storyline, you aren't tasked with saving the world, it's just stuff that happens. What you are actually tasked with is defeating the eight gym leaders and becoming a Pokemon master (well, technically, you are told to fill the Pokedex, that is the main storyline, everything else is just stuff that happens on the side, due to you not even knowing of Team X's existence until you meet them several times throughout the story).
I find that a lot of Final Fantasy games have rather good storyline, even with the spin-offs the storyline is rather good. Too bad that they are starting to screw around with the battle system, heard from my dad that they have just added QTEs. But usually the storyline itself is good, because it isn't just 'beat up stuff and take their stuff', that is Monster Hunter (kill creatures, take their stuff, improve weapons and armour to kill more stuff). As it goes, I find that most Square Enix games have rather good storylines.
I don't play Mario for storyline, I play it for the fun of platforming, as well as level design. Same with Legend of Zelda, really, there is some storyline to it, but I mostly play it for the dungeons and weapons... saying that, this thread is about storyline, and I have started talking about gameplay. Actually, Zelda games can have some rather sad moments, funny moments, and they have more of a storyline than a Mario game.
Sonic games can be rather bad sometimes, but I did enjoy Sonic Adventure and Sonic Adventure 2: Battle.