I imagine that a decently priced unlimited data plan is a big requirement for Apple in terms of negotiating with any provider. It might shake up parts of Europe, but I think that's what Apple would push for.
In the UK, Vodaphone offers "unlimited internet access" for £7.50; unfortunately their definition of "unlimited" is 120 MB per month. That is Megabytes, not Gigabytes. Others call 3GB "unlimited", which makes slightly more sense.
With the slowish Edge network, it would be hard for an iPhone user to exceed those 3GB per month by a lot, so AT&T can easily afford a data plan that is only limited by the network speed. For an iPhone using 3G and therefore technically capable of downloading say 40GB a month, I could imagine a data plan with a reasonable limit and reasonable fees if you exceed it. I don't think Apple would ever agree to something like 120MB per month.