Graphics card - what to choose?

Just upgraded my desktop from a Pentium G3220 and 4 GB PC3-12800 to an i5 4590 and 2x4 GB PC3-12800.

I can run Civ V Gold with decent graphics (built in intel HD 4600) but i was wandering what GPU I should go for if I want to MAX the graphics with at least 40 FPS even on huge maps.

My motherboard is a MSI B85M-G43 and my PSU is a CoolerMaster B500

Correct me if I'm wrong, but Civ5's framerate is CPU-limited, not GPU limited. On max settings, I can get maybe 30-40 frames per second dropping down to 10-20 later on with my HD 5850, 4GB RAM, and an outdated E8500, but when I look at GPU usage in Process Explorer, it rarely goes above 50%, even while CPU usage is at 100% and the game is sitting on about 4GB's worth of RAM+commit.

If you're looking for the fastest framerate, you'll need a CPU with a good cache size and a high clockspeed: a lot of Civ5's performance bottlenecking code (eg. the pathfinder) cannot run on more than one core at a time, so getting the most out of your primary core is paramount. Your CPU's 3.3GHz clock speed is a good start, but overclocking it and/or enabling turbo should help. Its cache sizes are decent (32 kB L1 per-core, 256kB L2 per-core, 6MB L3 shared), but cache misses will still be a thing unless you're running a Xeon-level CPU with 24MB L3.

Well Civ5 is very CPU dependent and yours is good enough but maybe you can still get something better if you do not run on the integrated graphics. Any GPU still sold would do the trick really for civ5. You could also try overclocking if you have a good cooling unit.

Yes, the bottleneck on Civ V is the CPU.

I have an i5 4460, OP your CPU is already faster than mine:
http://cpuboss.com/cpus/Intel-Core-i5-4590-vs-Intel-Core-i5-4460

My graphics card is a Radeon R9 270x 2G. You can check out my LPs (not the India one) if you want to see it in action. I record at 60fps so you should see what I see when I play.

You can use this site to see which GPUs are compatible with your existing set-up:
http://pcpartpicker.com/p/HwC44D

The R9 270x would work with your Mobo and CPU. You could probably opt with something cheaper as Delnar pointed out, as the CPU is more important in Civ.

CiV runs good even on cheap cards. The Nvidia GT610 2gb vram runs fine and that is only a $40 card.

I bought the i5 4590 after extensive reading online when your CPU was enough without being overkill. The extra memory was only because Windows 7, Civ V and HD 4600 used it all up ;-)
As far as I have read then a quad-core single threaded CPU with at least 2.8 GHz in "normal" and not turbo boost was what I was looking for.

I use the OC Genie that is part of the MSI BIOS.

I thought that I had to go up into something like the GTX 460 or R7 260x to have enough power.