I guess my question has two parts:
1. Where would you recommend going (ideally it has to be reasonably cheap)
2. What is access like from Hostels / Internet cafe's / Hotels?
In poorer countries you should be prepared for internet cafes that don't have wifi and in hostels and hotels the wifi often doesn't reach the rooms.
Generally the further you get from a major city the greater the chances of not having internet access.
Economic development is extremely uneven in South America compared to the US or Europe. If you're in a $2,000 a night luxury hotel in Buenos Aires, it's likely that it'll have adequate wifi hooked up to broadband. If you're in a $10 a night hostel in a rural area, you'll be lucky to be able to stand in line to check your e-mail on a shared 15 year old Dell with a CRT on a dialup modem.
Another complication is that even in many of the places with adequate broadband, access to locally hosted sites is reasonably fast, but there are very few overseas pipes leading out of the country. Hitting US or Europe based sites will usually be much slower than hitting an in-country site.
I've been playing a lot of Counterstrike lately, and apparently the game is wildly popular in Brazil. The average player from Brazil appears to have 200-300ms of latency, and when playing with them, the game suffers intermittent lag spikes.
This doesn't really give you an idea of the availability, but it should give you an idea of what your connectivity is going to be like when you are trying to interact with services in the U.S.