Nexus S anyday if you're ok with not having warranty. Else Desire HD is the way to go IMO.
You could also get ZTE blade for 40% your budget and use it for few months marking your entry to Android, then jump to Tegra 2 devices when they come later this year.
Android+ htc sense is very tempting...
After going through HTC sense video, I liked it very much and bought Desire Z yesterday...not a impulsive purchase but it feels heavy on pocket