I personally would steer very far away from a Galaxy S. It has a lot of problems with the filesystem being quite slow, have a peek at
http://www.google.com.au/search?sour...y+s+filesystem and you'll get a vague idea.
HTC Desire HD would be best in my opinion, however the new Nexus S certainly seems 'prettier' and the specs appear to match up quite well.
There are a few 'fixes' out for the Galaxy S lag issue, ie:
http://project-voodoo.org/lagfix but I've heard very mixed responses to it.
Edit: I know a few people with the Galaxy S, and be prepared to wait 20mins for the GPS to lock on