If your QS is from the original 2001 line, then the biggest HD you can use (w/o adding a pci controller card) is 128GB.
The 02 line did NOT have that limitation, as the mobo was upgraded to support any size of drive. As for RPM's, go for 7200 for the best performance.
However, if you want more sppeeeeed and are willing to spend a few $$, you could upgrade to SATA with a controller card......
With an 867/1GB, you should stay with Tiger for the best performance. Even though Leopard will technically install & run on your machine, it will not be a good experience.......
You could look on the marketplace forum, or ebay or cragslist for Tiger or Leopard, just be sure to get a picture of the disc first to be sure it is a RETAIL copy and NOT the grey/white restore disk that came from apple with some other machine.
DVD drives can be had just about anywhere.....I would recommend Newegg, TigerDirect or OWC......look for the Pioneer 106/108/110/112 series for max compatibility.
Formatting a HD is easy.....insert install disk, choose the "erase & install fresh copy of OS" option and let it do it's thing.....