Edelweiss
Guru
Go with T-Mobile. Data is free everywhere in the civilized world. T-Mobile will work on any GSM phone.
I'll second that. Travel extensively throughout North America and Europe and have excellent coverage (all unlimited), with free data, and phone is a hot spot. No extra charge. I do carry a second gsm phone with a European 30 day SIM card ($6) when I'm staying in Spain for several weeks, so the EU locals don't have to pay an international call charge to call my US phone.
(The one exception I found was Gibraltar. Due to a long running dispute between Spain and UK over the Rock, it isn't available there.)