I guess it depends on your budget but my ati 4890 works a-ok for me in game. However, everyone says that ati cards results in longer than usual load times because of some driver thing.
i'd suggest the 5870 if you have space and cash. 5850 if you dont have space but have cash. Not sure about the cheaper solutions. This game is really demanding