In the land of AT&T, the only "unlocked" iPhone is from the EU. However, you're more than welcome to purchase an iPhone either at full retail from the store or from someone selling their phone. Now you'll have an iPhone, sans a contract. This is where the fun begins. From a technological standpoint, you can now just plug your SIM card in and be on your merry way -- however, in reality, you'll soon receive a few annoying text messages from AT&T "informing" (read: threatening) you that you have an iPhone 3G that does not have a (specific) iPhone 3G data plan.
You can either choose to ignore this message, at the risk of accuring what I'm sure will be absurd network charges (which is what the SMS message you receive will be about) or you can upgrade to an iPhone 3G data plan. This is the part I can't wrap my head around. Like you, I wanted an iPhone. At the time, I had a Nokia N95-4 3G and an unlimited 3G data plan from AT&T for $15/mo. One would think, that unlimited meant just that -- unlimited. Wrong. It's unlimited for anything except an iPhone, which they'll now require you to spend an additional $15/mo (that's a total of $30/mo for those playing at home) for the iPhone unlimited 3G data plan.
Slick.
I only know all this because I just dealt with this headache about 2 weeks ago. Various phone calls, visits to the AT&T stores all yielded the same result -- nothing. So, I just sucked it up and pay the extra $15/mo like a good sheep. The only thing that keeps me somewhat sane is knowing that since I'm not under a contract, as soon as another carrier offers a suitable 3G network I feel comfortable on I can take my toys and go elsewhere.
FYI, AT&T will not under any circumstances unlock an iPhone (at least not at the present time). Regardless of whether you're under contract or not. Currently the only way to unlock an iPhone will be via the Dev-Teams recent breakthrough (which should be available Dec. 31st) or to buy one from Europe.