A new N800 can be purchased for between $200 and $230 online, and a used one on eBay for perhaps $50 less than that. This avoids paying for GPS, which you're probably not using on your desktop anyway :-)

Initially you would be restricted to the on-screen keyboard, but a Bluetooth keyboard could be added.

I don't think you're going to find any cheaper route to a full Linux, especially if you consider 800x480 to be the minimum useful screen size.

You'll probably be interested in the progress of such things as the Ubuntu port to ARM (an article in LinuxDevices, a thread here at ITT).