If your budget for a video card is limited, get this HD4650 instead. Unlike the one map01ch linked, it has DDR3 RAM, which moves it up a couple of tiers on the heirarchy chart: http://www.newegg.com/Product/Product.aspx?Item=N82E168....
Post your budget for suggestions on remaining components. The video card you can run may be limited by the size/quality of your PSU, so post the brand and model if you have it already, or let us know if it has to be included in your budget.
I would definitely go with that one. With the $10 rebate, it's actually cheaper. SATA 3.0 probably won't matter unless you plan on getting a solid-state hard drive, but as long as it's not costing you anything extra, hey, why not.
For a video card, the HD4850 at about $100 is tough to beat for the value. Paired with a quad-core CPU, anything lower than a 4850 is honestly not worth getting, because it'll be a huge drag on your system. If you were looking in the 4600 range, sack up and spend the extra few bucks, for chrissakes. The mid-to-low end of video cards is not the place to save $35.
An even better video card would be the 5770, but at around $160, I'm not sure whether that fits your definition of "budget."
The board you picked is fine, but yeah if you don't mind rebates the slightly more advanced model comes out cheaper. As for a cheap video card, yeah it depends on the PSU and your budget. If you have a cheap 500W unit or decent 380W unit then a 4850 or 4770 would be the way to go. The weaker the PSU the more I would lean towards the 4770 ^_^. If you have a PSU weaker than that, then I say a 5670 would be the way to go.