You're pretty emotional about these things. It is business. If you consider it from that angle, it might make more sense. Verizon was approached, but they probably wanted to plaster their logo on the iPhone and control all manner of elements behind the device (e.g. music sales). They probably also wanted to limit certain features which competed with or potentially interfered with their ideals. This was status quo for them before the iPhone, and they still do much of this today.
AT&T was a good option for them in the United States. As a GSM provider, it helped architecturally for expansion outside the United States (it isn't Apple's style to make so many different versions of their device as other mobile phone makers do). As a large provider, they provided Apple with a good pool of users to address. By offering AT&T something in exchange (an exclusive agreement), Apple received increased leverage in the negotiation, allowing them to do things like request special advancements and considerations for their product (such as visual voicemail).
AT&T gave Apple the chance to chance the mobile phone industry, and the opportunity to define the iPhone as the game changer it is today. And now, shortly, we'll see a Verizon iPhone, free of all the BS they might have wanted to permanently affix into it back when smartphones looked like Blackberries.