First off, visual voicemail. That's not just something on the phone, the provider has to support that. AT&T spent a lot of money setting up back-end support for it throughout their entire network. Second, AT&T gave them a deal unlike any deal ever made by a cell provider - they weren't allowed to subsidize the iPhone, it was for sale at stores outside of AT&T, it had online activation in the user's homes, some of the monthly plan fees were split with Apple... and they did all this based entirely on trust - nobody at AT&T saw even a prototype iPhone until two months before the announcement.
For all that, Apple signed a deal to make AT&T the exclusive US provider for 5 years.