Strictly speaking, of course, you can go anywhere from the start but you have better have tagged Stealth and put your first couple of levels into it because all your going to be doing is hiding. It is possible though. And, frankly, I LOVE that most things don't level with you for so many reasons. It's better for immersion. You don't get the idiocy of highway men in Glass armor like you did in Oblivion. You also get the immersion of real areas that are wilderness. Places where no piddly NPCs stroll through because they'd get waylaid too. You get the satisfaction of so many many "I'll be back" moments later in the game where you got schooled by an area but now you're coming back and you're going to waltz through that gang camp like the Terminator in a police station laying down some serious havoc.
I think, for me, that's what it comes down too: satisfaction. Auto leveling takes that away for me. I feel that FO:NV better rewards my leveling and in that way I actually feel more powerful and more accomplished when I can come back to a place I was unable to handle early in the game.
But for anyone who feels the beginning is too linear I'd say give it time. You could also rush right through the main quest and get to NV pretty quickly I'd say but I've been doing every sidequest I can get my hands on and exploring the south as much as possible. I've got probably 25+ hours in and hit level 10 and New Vegas just last night.