I'd recommend starting with a minimalist-leaning shoe, especially if you're brand new to running, and then phase in barefoot or more barefoot-style running as you go. I used to be a pretty serious 50+ mile a week runner, and I would recommend last season's Saucony Kinvara or something in that direction to start. If you don't mind ridiculous colors, you can get them for 40 bucks. If you're transitioning from traditional running, or wear dress shoes generally, it will be a rough enough start. I wouldn't start up with anything less minimalistic.
If you do go more minimalist later, I've had great luck with NB100 (they have several diferent versions), again quite cheap online. But the last thing you want to do is cut your running career short before it starts. I'd take a close look at what your foot is used to now (do you wear hard-soled shoes mostly?) and just go a step or two below that to start.