In FO3 you get most of your EXP for killing enemies and finishing quests. In Skyrim almost EVERYTHING you do, from fighting to brewing potions to buying items somehow contributes to your character getting stronger. This is handled better than in previous Elder Scrolls games too. It complements the sandbox nature of the game perfectly. This is one of the very few games where you can just do whatever and get rewarded for it. No matter whether you're focusing on the main quest line or just exploring the world there's always a sense of progression. FO3 felt more like a linear RPG with a main story you're supposed to complete and sidequests that act as diversions, exploring and making up your own goals wasn't nearly as fun.
The manner in which my character levels up does not have significant bearing on "fun" for me. I wouldn't care if there was no leveling at all, just acquirement, though admittedly leveling did get more thorough in its approach this time around. Actually, since the skills I mentioned aren't worth a damn for such a long period, this impedes my freedom to have fun "any way I like" and I'm running around being more of a warrior than a thief. I have mostly disdain for the typical "leveling" system found in more rpgs, but that's a whole other discussion.
I also don't follow how Skyrim is "less linear" than FO3; it has a linear main quest just like any other game, though with a greater number of sidequests. Shit like "making up your own goals" is for the birds; you can do that with any game.
I thought the combat in FO3 was flawed as well, but I enjoyed the pace more, and I liked the environments, characters, plot more. Did not like New Vegas that much and didn't bother to finish it.
But your bringing up the "sandbox nature" reminded me of something - I don't understand the obsession with pure sandbox games. Procedural generation is nice because that element of randomness guarantees replay value with a more consistent challenge, but this "create your own adventure" angle puzzles me. How do you expect to seamlessly weave your own narrative in a video game? And I do mean IN the game. It's easy to write progress reports and background story to yourself in D&D fashion (players of Dwarf Fortress have done this), but ultimately the game is pretty indifferent to any notion of "story" unless you let the gameplay itself represent the story that unfolds. Any in-game scripts will
reveal redundancy and limitation, whether you think they're linear or not. At best you can get D&D in a sandbox, letting players set the background, tweak some mechanics, and be responsible for the dialogues themselves. Games with map-builders, e.g. Starcraft or Knytt Stories, allow this to an extent, but everything is pre-determined, and that's not what the search is for. Ultimately players will be dissatisfied because they want the game to do more of the work; they still merely want to weave through a storyline, but want it to change at their whim in any way they desire. That'll never happen.
We already have games like Minecraft that have you "create your own fun", which is kind of like virtual Legos. And the Sims - virtual Barbie and Ken. I find this exceedingly boring. I'll take linear gameplay and script any day of the week if it's done well. In the end, all of my favorite games are, random are not, driven by linear experience.