How's the crime and safety situation in Colombia recently? Many years back a good friend of mine lived there for a significant amount of time and it seemed quite unsafe.
I love the Colombian caribbean coast, so that is why is my first recommendation to the OP, the weather is perfect almost all year round, and with a modest budget he can definitively have a moderate (and even higher) lifestyle with no much compromises.
This means to assure that you can get a solid tan before the arrival, keep a low-key profile and try to keep your mouth shut in crowded places to hide your non Colombian accent, even if your Spanish is fluid.