Ubuntu 10.04 LTS, accept no substitute. Maybe use a Ubuntu 10.10.2 desktop to manage them, it's easy to use. (11.04 is still unstable, IMO.)
It actually all depends on what packages you plan on running. Then cross reference that against what your options are, I think you'll run out of options quickly, TBH.
And you just need putty on the windows side. But, if you have to, all of them can run x-windows generally these days. I just find Ubuntu to be the easiest, plus their packaging system is the best, being Debian under the covers.
Please note, these are opinions, and I'm entitled to my informed opinion.