From my understanding, even though EDGE is a technology every wireless carrier can cover, ATT is the only one in North America really promoting it. It is possible to access the internet from WiFi but if the iPhone is only compatable with EDGE in the USA, ATT could have better assurance over who used the phone and on what network. I'm not claiming this is a bulletproof argument, but that could be the reason Apple only included EDGE; to satisfy ATT.
Pretty much every GSM carrier in the US I've ever used (AT&T, T-Mobile, Suncom (while roaming), etc) has rolled out EDGE.
I use it regularly with T-Mobile and generally get download speeds of anywhere between 30 and 80kbps. EDGE's real problem is with latency. No amount of bandwidth upgrades at the towers are going to help with that unfortunately. Latency makes a massive difference in both how fast something "feels" and even to some extent how fast it actually works: when browsing the web, you're typically loading many, many, objects, when downloading one webpage; and the higher the latency, the higher the delay before each object can actually be transmitted to your browser.
Latency is also why most current 3G standards aren't as pleasant to use as even the slower forms of DSL, though both the 3GPP and Qualcomm are working on serious reductions on their latest versions of UMTS and CDMA2000 respectively.
Don't expect anything decent on the iPhone regarding cellular data until the first UMTS version. And don't expect anything genuinely comfortable until the first HSUPA (one of the low latency enhancements to UMTS) or 3GPP rel. 8 version.