I think there are a lot of factors at play in determining what you want.
My first notion would be to recommend an Android handset. Reasons being that they are simply on every carrier at the moment. That said, you need to pick a truly good Android handset, and make sure it's going to be updated to 2.3. Here's the thing about Android. It's great, especially if you are a tech person, but it's not the most user friendly in the world. It's also still in a bit of the famous "beta" mode that Google tends to do with their products. They are quick to make improvements and updates, but it's a fast moving/changing scenario. If you are on AT&T, I would avoid their Android sets. They just aren't there yet since they (at the moment) still have exclusive rights to the iPhone.
I have an EVO (Sprint) and think it's a great phone. It's a bit big, but still rocks. I got it when I bought a 4G plan from Sprint just so I can have great internet for my work laptop all over the area I live/freelance in. I use it mostly as a work/backup phone.
That said, as far as fit and finish, ease of use, and games/apps go, the iPhone4 is my main phone. It's awesome. I don't like AT&T, but that's how much I love my iPhone. I am fairly tech savvy however, and have jailbroken mine to open up the few options I enjoy on my EVO. Main one being tethering and wifi-hotspot.
Now, as far as AT&T is concerned, here are my thoughts. Everyone will be moving to 4G soon enough, but if you aren't in a decently urban area, I wouldn't even factor that as a plus at the moment. It's going to be a while before 4G is mature.
Also, mark my words, because there is a lot of hype and disagreement about this, but when the iPhone goes to Verizon later in 2011, you can bet that there will be a whole new load generated for Verizon's network.
I get around 3Mb down and 1Mb up on my iPhone, on my EVO (in sprint's 4G areas) I average about 5.5-7Mb down and 1.5Mb up. Now, in areas where I go to 3G on my EVO (which is pretty much EVERYWHERE 4-5 miles outside all metro areas, my performance is WORSE than the iPhone.
Hope this isn't confusing. I'm just spewing random experience and facts out there, but I hope it helps.
My mother went through 2 'droids before I gave her my old iPhone 3Gs and she uses it more than I could have imagined.
I would personally have a hard time giving up either of my phones, but push come to shove, I would let go of the EVO for a few main reasons.
•I REALLY appreciate good industrial design and LOVE the feel of the iPhone in my hand. It's like an old leica rangefinder camera.
•I am an app whore and I love the amount of options in the app store, not to mention the games selection. That new EPIC game is hands down amazing example of what's to come for handheld gaming. I truly looks like an xBox 360 in my hand)
•I run mainly Macs in my day to day (designer/illustrator) and so the syncing ability of the iPhone with my Mac is the best experience out there with a phone
•All the menus, subtextual items, etc just flow great IMO. The UI is interlinked so well with every other application that it's amazing.
Take those 4 things into consideration. They would push your buyers choice either way.
PS, don't discount a new Windows phone. You really should go try one out. I was really impressed (and I HATE using windows in general, although windows 7 is a HUGE leap forward from vista) and it actually does a good job of staying out of your way similar to the iPhone.
Hope any of this helps,
technocoy