First, companions. Everyone used them at least one time, and liked it (I hope). The mechanics that Fallout: New Vegas used were great. Companion Perks were balanced; you can get any job done without them, but they still offer great bonuses. The companion wheel made commanding your companions seamless and effortless (provided you can activate them), and if you didn't like the wheel, just select talk and you could then command them through dialog.
Second, the improved trade system, which was actual bartering, allowing you to buy and sell multiple items in the same transaction with the game showing you how many caps you would get or give at all times. Combining a trading system like this with the disposition system of a TES game along with an ability to haggle would make trading really interactive.
Third, Factions. The factions of New Vegas allowed you to make alligences and feel like they are really effecting you, because, you know, at certain points new dialog options would open, enemies would actively hunt you down, you obtained support options from allies, and other great things.
Fourth, Actively traveling traders going from town to town and seeing a new inventory each time. This, among other things, would really make it worth running your ass from one tow to another instead of using the fast travel system.
Fifth, Random Encounters. These would make the game more interesting each time you played the game, because it would change up the gameplay experience each time you re-rolled a new character. In Fallout 3, I was always heading for the GNR station by that supermarket, so it was always interesting what the game would throw at me each time I played through. New Vegas kind of lacked that, but was able to make up for it by allowing the player to pick the wild wasteland trait to mix up the game a bit (Holy Frag Grenades FTW).
If anyone can think up other improvements to the overall free-roam experience that the last two Fallouts gave, post them.