OneFiercePuppy: Sounds like you'd really appreciate at least two of the four DLCs for New Vegas, if you haven't already played them. Honest Hearts and Old World Blues are very dense and directed without ever feeling like you're on rails. Lonesome Road wraps things up nicely and is a good closer for the story, too. You should be able to get the DLCs for about a buck apiece on sale. I'd really recommend, based on what you're saying you liked and missed in FO:NV, that you keep an eye out or them, if you haven't already played them and think you could tolerate another play through of New Vegas.
I've played them. Lonesome Road was interesting but still lacked any major mystique beyond the central character, Honest Hearts I really didn't find all that great, though Old World Blues I definitely wish I spent more time on. I plan on doing so when I get back to the game, but neither were that memorable on the first go around. OWB particularly had so much dialogue, funny though it was, that getting to the point was a major issue. There's a lot to discover, which I appreciate, but it's perhaps a reverse problem of the rest of the game. Too much to do in not a big enough space, and having to do the same thing multiple times just to get all the endings.