Depending on current hardware costs...
Dual Xeon 3.0ghz (give or take)
Good hardware based raid controller (preferably 3ware). It should be configured in RAID10
64 IP addresses
APC reboot port
$750/month + $399 Setup.
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.