Depends on how you define 'Best game storylines'. Some games have great gameplay,while bad storyline,and vice versa.Some games have both great gameplay and storyline to compliment it to be a great game.Games that have great storyline are:
1.Final Fantasy games have great storylines and gameplay,but not all FF Games appeal to me,like Final Fantasy Tactics and Final Fantasy XII.However,graphics,storyline,music are top notch for almost all of FF games.Square Enix games are great,and I hope they will continue making games.
2.Resident Evil games are long standing series,with great storyline and gameplay,especially Resident Evil 2,Resident Evil 4,and Resident Evil 5.However,as Resident Evil 4 and Resident Evil 5 doesn't have any zombies as regular enemies,some long time RE fans are disappointed with the story going on and the new enemies (Ganados,Majinis),which are considered to be smarter and stronger than zombies.Probably one of Capcom's well known series.
3.Metal Gear Solid games have interesting storylines which connect to each other.The games are well known for great storylines and wonderful plot twists.The games have incredible gameplay too.Those plot twists are usually surprising,as expected from Hideo Kojima,who works for Konami,and now owns his own company.
4.Devil May Cry games have wonderful storyline,except for DMC2 and probably DMC4.DMC4 doesn't really answer any questions in past games,but instead a new character,Nero is added to get more new DMC fans.However,DMC games gameplay are top notch and the dark and gothic storylines are wonderful,especially DMC and DMC3.Capcom did great for these games.
5.Shin Megami Tensei games are known for occult themes,like angels and demons from various religions and mythologies.Many of SMT games have superb storyline and gameplay,like Digital Devil Saga,Digital Devil Saga 2,Lucifer's Call,Persona 3 and Persona 4.Atlus made wonderful jobs at making these games.
6.Kingdom Hearts games,are probably one of the mysterious game series,with many mysteries left out in their games.You may call KH games are for kids,but the story is wonderful and superb.Can't wait for new KH game from Square Enix.
It depends on your point of view how and what gams do you think have great storylines,and every companies have their pros can cons for games.These are all my opinions,and I think all the game series I mentioned above are my favourites,in storyline view.There are still more games series that I liked,but those are enough for now.