I'm going to toss my opinions in the ring as well.
A shared Linux host definitely will not suffice. Alot of times they will send you an email stating "over usage of system resources". While Moodle isnt a "bloaty" web-app by any means, it is heavier than most apps.
We anticipate about 20,000 students (eventually) in our installation and we have purchased:
2 x Dell 1850 1Us (2x Dual Core Xeons @ 3.0, 2GB Ram)
1 x Dell 2850 2U (2x Dual Core Xeons @ 3.0, 8GB Ram, 4 x 320GB 15K RPM SCSI HDs in RAID-5).
We have all of those set up in a TCP load balancing configuration.
Just to compare speeds, we have a little test/development server here in the office, it's a 1.2ghz Athlon, 512MB ram. We did some simulated load tests, and after about ~30 concurrencies, things really slow down. We've even done some apache tunining and tweaks (PHP eAccelerator), and some MySQL
With that said, You're going to need some hardware to support 20,000 students efficiently.
Not to be overly negative, but there are some additional hidden costs: Bandwidth, Power, and as Michael said: Support staff. Also, another little hidden cost: Teacher Training. However, with all of this aside, this will cost less than blackboard or any out of the box solution. Also, with the availability of the source code any PHP programmer can easily modify your Moodle.
Best of luck!
Mesa Public Schools, Mesa Arizona