I used to live in NYC, and even there I was able to keep down my COL. I was lucky enough to grow up there but I found an apartment for pretty cheap in outer brooklyn. I didn't go out to clubs much, or eat out much either. I hung out mostly in cheap bars or dinner/house parties with friends.

Right now I am in South America, I am using couchsurfing.com and using hostels. I have an apartment right now which cut down costs a lot but still hang out with the local couchsurfing community. I cook nearly all the time so food is pretty cheap. I am lucky that I can program and work remotely but I have friends who do data entry work, translation, english tutoring. I have friends who volunteer in hostels for free room and board or use http://www.helpx.net/

As for traveling, mostly by bus, or budget airlines(which are as expensive as buses). And I do not move often.

Hanging out with couchsurfers has really kept my daily COL. I personally hate most tourist traps and by hanging out with couchsurfers usually you get amazing local cultural experiences for either free or cheap. IE My host in Venezuela took me to his girlfriend's niece's baptism party where I sang, drank, and danced with 70 year old venezuelan women.

I find I am happiest not going on a guided eco tour, or going to the top of some tall thing(building or mountain), but sharing thoughts and experiences with different/local people.