You're in luck! That machine will run Mac OS X 10.6 Snow Leopard, available from the Apple Store for $19.99. The Apple Store now has guaranteed next day delivery. Installing is very simple -- just insert the disk and hold down the c key on boot and follow the easy on screen instructions. Installation should only take 20-30 minutes. If you need help installing, you can take it to any of the Apple Retail Stores and they will install the System for you. But there is still plenty of online support from Apple and the web to get you back up and running quickly.
If you want to run a Linux or Windows desktop, since the hardware supports virtualization, then I still recommend leaving Mac OS X intact on the hardware, and, unless you need it for gaming, run the other systems in a virtual machine. This way the systems you work in will fully support the hardware, and there will be no performace degradation. With virtualization software like Parallels Desktop 6 for Mac you can run virtual machines in full screen, and never even know that OS X is running. Also available for free is Virutal Box; here is a download link for a version that will work in Snow Leopard.
Once OS X is installed, you can also install Windows or Linux directly on the hardware using BootCamp, and have a dual+ booting machine.
In general, its a good idea to leave Mac OS X on the mac hardware, as removing it will reduce your options.