well, I'm an Ubuntu fanboi, so I'd recommend that (especially if you've never run linux before)

I've never understood the whole this-distro-for-this, this-distro-for-that mentality
some ship with different desktop environments, some use different package formats
but frankly, they're all much the same

Ubuntu will get you up and running inside half an hour

Ubuntu min specs are here
https://help.ubuntu.com/8.04/install...are-reqts.html
as you can see, the recommended specs are 512Mb Ram, with 5Gb of storage space
basically, any desktop machine you buy will meet this no problem

Just a few points....

- I personally would recommend an nVidia graphics card over AMD (ATI)

- I would just make sure (quick google) that the wireless card in the machine is ok under linux (the vast majority are, however there's the odd one - broadcom based wireless cards can be an issue - that may not work instantly out the box)

Also is it possible to screw up windows by messing around in linux?
Short answer is no
long answer is, yes you can, but you'd have to really try - there's next to no chance of you messing up windows unintentionally

Can you run more than 1 kind of linux on a computer at the same time?
Yes, using something like virtualbox

How hard is it to set up the internet?
dead easy
it should just work (bar the odd problem with wireless cards, as above)
if your wireless is encrypted, make sure you know the key / pass-phrase