I'm looking to procure a PC for the express purpose of displaying video content from a Synology Surveillance Station. This PC just needs to run Windows and have enough horsepower to play back several 640x480 feeds at ~10FPS at one time.

What should I aim for? Should I be looking at a faster CPU or better graphics? I thought about purchasing a used Core i3 Optiplex and throwing an inexpensive mid-level graphics card in there.

What do you folks think?

I'm thinking you should look at the various all-in-one iMac-clone products. Assuming this is going to one of your clients, might as well have the clean one-box install, and a touch screen for extra grooviness.

Haha, yeah that's a possibility, but the PC versions of those are usually super crappy, at least from what I've seen. The good ones are really expensive, which is not what I'm looking for. I'm trying to replace an existing computer that's way too underpowered for this job (like, it's 7 years old and can't really play Youtube videos smoothly).

I think the smallest NUC will do.
Do you need live video feeds on display and, if so, how many? NUC offers the opportunity to add a large monitor to it.

Yeah, I need the live feeds. Right now it's just two but could get up to ten or twelve at the max. As more feeds are added, the live resolution would be decreased to save bandwidth and improve performance on the playback machine. Everything is recording to the recorder at 3MP, though.

12 feeds will require, IMO, either a >=24" monitor, or two monitors, for the feeds to be useful in live view.

A NUC will let you use as big as a monitor you choose, and in my experience will run the feeds nicely if you go with the top of the line.

Any all in one system will limit your monitor size/resolution, unfortunately. Otherwise, I'd suggest to look into those as well.

I am not sure a NUC supports multimonitor, but it will definitely via USB3 at least.

Also, you can attach it to the back of a monitor compatible with VESA arm suppors, saving a lot of desk space.

I am currently using three different NUCs at work, for very different projects, all running Winosws 8.1, and 1 at home as a HTPC, and they all proved extremely reliable in the last year. They are very nice machines.

I'm very interested in NUCs, but I'm not sure they're necessary for this project. I'd have to pay a premium for the small size, and that's just not neccessary here. To be honest, the video feed display is going to be used almost entirely as a deterrent. This location has a lot of people coming into the office, potentially casing the place for when they come back. We want to make sure they see a screen with shots of the property on it. We're not going to have someone sitting in front of it all day looking for things. For that reason, it could just switch between feeds, in which case I'd just need to show about 4-8 at a time. I figure most mid-level computers could do that, but I'd still like to figure out whether I should focus on CPU or GPU power...

GPU, I would say, but really, video feeds are not that power hungry. My guess is that any I3 with Intel HD4000 will be more than sufficient, and I doubt anything new is going to be less than that?