The answers will have to differ for internet cafés/hostels versus flats. I'm interested in both answers.
Short answer: It depends.
Long answer: If you are traveling to important cities (Bogota, Medellin, Barranquilla, Cali). The norm is a 5mbps minimum. In towns far away from main cities, could range from nightmare to 10mb. 3G coverage in most parts of the country is generally good.
According to the Netindex list, where Colombia is on number 105, the average download speed is 5.45Mbps. The list doesn't distinguish between internet cafes, hostels or flats.