VPSes did not exist as a commercial product in 2000. Back then you likely purchased and colo'd your hardware or leased from a provider. You could get shared hosting with CGI access but that was about it.

Shared hosting (with PHP, mod_perl and SSI) was available from thousands of providers for between $5 and $25/month. SSL required a dedicated IP, because SNI wasn't a thing yet, and so if you wanted an SSL enabled site, you were looking at closer to $100/month. But that was for managed, shared hosting, typically with access to a database and automated backup. Good enough for most businesses small-ish web presences.

Rackspace offered dedicated servers for $150/month and up. Smaller providers would rent you a server in their datacenter for around $60/month. I used a company called sagonet in the early 2000s that is still in business and still offering a similar service for about $30/month: http://www.synergyisp.com/dedicated-servers/

Most larger companies at the time contracted with a colocation provider and purchased servers for between $1000 and $4000 each, and paid in the neighborhood of $1000/month for a rack, or $500/month for a half rack, including power and network.

This was monumentally cheaper than the AWS based stack we have these days, though - no company with any complexity to their website has a $40/month AWS bill. A company with a similar SAAS offering to what I ran in 2001 for $40K up front and $500/month is probably looking at a $5000/month AWS bill at today's rates.