Kinda sorta a sci-fi game, it's not full on Star Trek sci-fi though but Deus Ex Human Revolution has an amazing story. Skyrim doesn't have the greatest story but it has quite a few of them. Dragon Age: Origins has a nice story.
I have asked a friend about Shaya and he says it's good, but I seriusly don't know since I haven't tried it. You can try it out and see for yourself
•Dragon Age: Origins •Kingdom of Amalur: Reckoning •The Witcher I find those 3 not boring, esp the witcher.