This is a great ref for video cards. Look both at their recommendations and the 'hierarchy' chart. It's not perfect, but should get you in range. http://www.tomshardware.com/reviews/gaming-graphics-card-review,3107.html
I'd change the video card first, and only touch the CPU if the video card does not help.
If there is a game you particularly want to play at high frame rate then see if it is video card or CPU bound. If you can tell post the game and someone will look it up.
For buying a video card, can you hang out another few months? AMD cards are currently selling for more than they did before christmas -- the bit coin miners seem to be buying them up. At some point supply will catch up with demand and prices will fall sharply to what they were or below. Nvidia prices stay in the same range as AMD prices (+/-) so they will also go down.