Video game stories are cliched. Deal with it. If you tried to have a realistic plot there wouldn't be a game to play. If none of the factions trusted you in Fallout New Vegas you wouldn't have had anything to do. Period. Likewise, in Oblivion the fate of the empire and the trust of the superpowers was given to some random prisoner. Fallout 3 had no decency in its ending, it forced you to choose one side and then killed you off; absolutely pathetic by the standards of any RPG, which is why they had to come back and fix it up (somewhat) with Broken Steel.
Also, if you have a problem with being limited to dialogue and notes, go play some other game then. In Beth style RPG's, you are limited to dialogue and notes. Personally I like the way in New Vegas they used this to make you choose a side based on what you can learn from the biased opinions of others.
I don't have too much problems with Cliche's in they're handled properly. Having character's behave stupidly for the plot to work when they're supposed to be smart, Caesar is supposed to be a great conqueror the likes of Alexander the Great and he shows no sign when he trusted you, worse is that he's a man who isn't afraid to sacrifice a peon and he could do that to check if you really destroyed the robot factory under his camp.
You don't need to make the factions stupid to make them work. Games like Mech Warrior 4: Mercenaries and Tachyon: The Fringe had factions and portrayed them is competent and powerful, they just needed a Hero to push the scales and end the stalemate. Both games worked out Rather well, they weren't about the stories and
more about gameplay but they didn't have to make the factions to be stupid to make the player matter.
Beth RPGs offer exploration, that's why I play them. I don't mind the stories too much since I really like to go out and treasure hunt, though they have been improving in their story telling, They offered some great show; not tell moments like Growing up in the Vault, the consequences on the choice of saving or destroying Megaton, Finding your Father and your Father's sacrifice in FO3. Yes the Ending svcked but the path to it had some really great moments.