I've owned 3 Shuttle SFF systems so far, and I love them, so I'm going to be biased in their favor, and would recommend the Shuttle out of the 2 choices you have, except for one thing. It's AGP. Do NOT buy an AGP motherboard at this point in the game. You won't be saving a ton of money, and you're destroying your options. It also is very silly to buy a new (or new-ish) AGP video card, since you'll have no chance to reuse it on your next system, when AGP will undoubtedly be out of the picture. (unless you build systems every 2 months).
However.. I think there is one important thing to mention here. You are looking at very little upgrade options with your system if you go s754. If that is ok with you, go ahead and buy one of the ones you list, but I'd really consider a s939 system so that you can have many more options for upgrades in the future. Sell your s754 CPU on Anandtech or eBay or something, and put it towards a s939 chip.
So... my recommendation...
If you know for a fact you are 100% sure that you will never upgrade your CPU and you're ok with buying a video card you won't be able to reuse, get the Shuttle you linked to. It's a very nice case, easy to work with, and its very neat looking in person.
If there is even the smallest chance you will upgrade the CPU in your system, sell that s754 chip you have and start fresh. You can get a nice s939 3000+ for dirt cheap these days and you'll have a ton of headroom for upgrades. Same thing goes for PCI-E. Go PCI-E unless you plan to keep this new system for years and years. It just doesn't make sense otherwise.
My roommate at college has a Shuttle SN25P, which is a s939 board with PCI-E and it is AWESOME. Looks great, easy to use, has room for 3 hard drives. I highly recommend it if you can swing it.
As far as video cards, ATI looks really good right now on the high end side of things, but for your price range I'd get something in the Nvidia 6600/6800 series or something in the ATI x800 series.