EVDO is nice for navigation programs, maps pop up a bit faster. Tethering is obviously much better. Web browsing is slightly faster, most of the limitation there is the device itself and its rendering of pages.

Sprint and verizon have had world capable phones for years: nextel i930, samsung ip-a790, samsung ip-i830, motorola a840 etc... They compare poorly to just getting your own unlocked GSM phone for travel but they work.