Depending on current hardware costs...

Dual Xeon 3.0ghz (give or take)
4GB RAM
4x120gb sata
Good hardware based raid controller (preferably 3ware). It should be configured in RAID10
Fedora Core2
64 IP addresses
APC reboot port

$750/month + $399 Setup.

Data:
100gb $275
200gb $375

EDIT: Will have to do the sums on 500gb + 1000gb, I think the price I quote is dead wrong.

You'd find it cheaper to lease a few P4 3.0Ghz with 100Gb each then leasing a highend box.