charlight: I am still on my first play through of Fallout New Vegas. This is actually the first game from Fallout franchise I have ever played. I am having a great time! There is a story, but the fact it is so non-linear means I usually discover things and places in the wrong order. Also I tend to wander off and get lost a lot. A LOT. This has caused me to fight more/stronger creatures than the story missions intend. Therefore when I finally do find the story missions I feel over powered. I honestly had about 16+ hours put into the game before I learned that there was a fast travel system. Lol
*Spoiler alert* For example, when I got to the casino that had Benny inside. (Benny is the person who shot you in the head before the game began) The guards at the door said to hand over my weapons. I decided to test my luck/skill and just kill them. I literally killed everyone in that casino. First try. Looking at the loot, I think I was supposed to be stealthy and steal his room key, then kill him in the night. *Spoiler Done*

Gazoinks: Yeah, one of the coolest things about NV is how flexible it is. Besides children, there're only two (or maybe 3, I forget) unkillable characters in the game, which basically ensure that you won't completely bork the story, but otherwise you can go on a constant murder spree if you like. Which is an extreme contrast to Skyrim where like 75% of the population is unkillable.
You should definitely check out the other Fallout games afterwards, as they all have that non-linear story approach. Though FO3 does the whole Bethesda level-scaling thing so you won't usually fight guys significantly stronger than you.
I've actually never played Skyrim either. Or Oblivion. I'm usually not a fan of these open world style games. I have terrible orientation skills, so any game that allows me to go too far off the beaten trail normally frustrates me. As a general rule, I don't like feeling as though I have no idea where I am or what's going on. However Fallout feels different, although I can't quite figure out why. Don't get me wrong, I'm not blaming the games. It's not their fault I get disoriented and lost so easiily. It's normally not my genre. I usually go for more linear RPG's. Like mission can be solved in different ways, but you start/finish the missions in the same order regardless of your play style. Would you happen to have any suggestions?