1. If you want to stick with AT&T, then the HTC Aria seems like a reasonable phone. AT&T supposedly somehow prevents you from installing apps that are not on the Market, but you can still actually load them using the Android SDK. That said, I think I've maybe installed a total of one application that didn't come from the market. As far as I know, T-Mobile's the only other GSM game in town, and they don't seem to have any cheap Android phones available, if that's an issue. The Aria and all the T-Mobile phones I've looked at are all quad-band. I don't know about AT&T's policies. I know that T-Mobile has a no-questions asked return policy, but it's 20 days, not 30.

2. I have spent $0.00 on apps. There are a few I have considered paying for, but I figured that if I was still thinking about it a few days from when I considered it, then it made sense to buy it. That has yet to happen.

3. Like Caleb, I don't really do syncing, but I'm sure that there's something available. A quick glance at the App Market seems to show a few. Check out the external links on the Android Market Wikipedia entry for PC-accessible interfaces to the Market so you can look for yourself.

4. No reason you need to, IMO. Some folks dislike the modifications that vendors make, but most of them aren't terribly invasive, AT&T aside. Everyone seems to really dislike the MOTOBLUR "UI", FWIW. Some folks like the HTC Sense UI, others dislike it.

So, recommendations: Try to find a phone that has the normal Android UI. If you can't do that, at least avoid MOTOBLUR. Try to get one that is on Android 2.2. The JIT compiler under 2.2 is a significant improvement. Failing that, definitely avoid phones stuck on anything less than 2.0, and try avoid any phones that are less than 2.1. You don't want to get something that's already been obsoleted.