I bought a 3,1 (2008) a couple months ago. You're right about the CPU, I did exactly what you describe, CPU and heatsink from eBay. Don't forget to buy a very long handled hex driver (about £5-6 from Amazon) and some Arctic silver paste.
I followed this guide:
https://www.ifixit.com/Guide/Replacing-Upgrading+Mac+Pro+Processors+(Early+2008)/17562
Long handled hex driver:
http://www.amazon.co.uk/gp/product/B0080R1UC2?psc=1&redirect=true&ref_=oh_aui_detailpage_o04_s00
Mine came with an SSD drive that is in drive bay 1. From what I've read SATA II is limited to 250 MB/sec. I'm guessing if you use a SATA III PCIe card you will reach closer to what the SSD drive specs are. I'm also toying with adding a PCIe SATA III card, found this article, really useful although applies to a 2009:
http://pindelski.org/Photography/2013/09/07/mac-pro-2009-part-xvi-3/
Yes your 500 GB drive should work fine. Just mount it on the existing drive sled and slot it in.
I bought an Inatech USB 3.0 PCI card, not really had a chance to test it much.
I added a Geforce 750 ti with 2 GB RAM, seems to work great, no boot screen, but not a problem as I have the older Mac specific card (forget the model) still installed should I need the boot screen.
So far really liking this Mac Pro, so much expandability, makes me wonder why I didn't get one sooner.