Alot of it depends on whether or not you're building the machine yourself. I just built a new gaming rig and only spent $800 on a machine that runs Crysis at very high, 4x AA, V-Sync, 1920x1080, at 45fps avg. Granted, I had a 1TB HDD and the OS already, so I didn't need to pay for those. The parts I got were motherboard, 8GB 1600 RAM, i5 2.8GHz quadcore processor, 2x5770 ATI cards in crossfire mode, full sized ATX case, H50 water cooler pump for the processor, wireless pci card, dvd drive, 750W PSU.
You could shave costs by getting just 1 graphics card and 1 set of RAM, reusing a HDD, dvd drive, and OS, not getting a wireless card, getting a smaller motherboard that doesn't support 2 pci-e 16x ports, smaller case, reusing a PSU (not recommended), getting a less expense processor, etc... I think I could have built an even cheaper machine that would run the games described above for around $500. Any less than that and the machine you're getting just almost isn't worth it as you will simply be getting a new one in a year or two.
I will say february had some great sales on. All of those parts would probably be around $1100 now, but there are other sales on at different times. Ultimately I lucked out when I built mine. I'd check newegg, microcenter, ebay, tigerdirect (even though they were far more expensive for the same parts when I was looking), maybe even amazon.
Adding to the discussion about monitors vs TVs, I've found that most "Primarily TVs" have issues with Text display. I have a 46" 1080p TV, but text looks aweful through HDMI (guess I haven't tried DVI). 36" probably wouldn't be that bad as the same resolution means the same number of pixels, means the pixels are smaller and will seem sharper. My 46" works great for the 360, but not quite what I wanted for PC gaming. So, I ended up buying a 23" monitor (updating from my old 19") for this machine. Brought my total cost up to about $1k for my entire system which I am quite happy with!