The cheapest servers are at rackshack.net.
At the bare minimum:
http://www.rackshack.net/english/amd.asp
AMD Duron 1 ghz, 512mb RAM, 40gb hard drive and 400gb of bandwidth. $1 setup fee, $99/mo
However, with that kind of configuration, server performance may be pretty hard to keep at a reasonable level.
Ideally, one of these.
http://www.rackshack.net/english/hpp420.asp
P4 2.0, 512, 80gb, 400gb, $179 setup, $129/mo
However, with the cheapest servers also comes the lack of service.
We would also have to hire a Linux server admin which can range anywhere from free w/ hosting to hundreds of dollars an hour.
When is flexible. When just depends on when we get the money flow.