We live in a very expensive place (Hawaii) and I can tell you there are lots of ways to drop your spending much further than you would initially believe.
When we moved to Hawaii we were told it was too expensive and we would never save any money. We are saving more now than when we lived in a low cost area!!
How, you might ask? Well, expensive areas tend to have lots of free stuff to do. In our case, that involves surfing, hiking, etc. In other expensive areas (DC, SF, Seattle) there are things like top notch libraries, museums, etc. And amazingly, those locations have outdoorsy-type stuff to do in close proximity to the city! Hiking, camping, etc.
For us, quality of life was paramount. We knew there was a chance our expenses would have a negative impact on our savings rate. But over time you learn where the good thrift stores are, you make great friends who would rather have a beer at the beach at sunset than go to happy hour, etc.
In fact, it's very possible that if we were living in a midwestern city with low COL but long, cold, grey winters (which is where I grew up!), our spending would INCREASE because we might feel the need to go to movies, out to eat, and other silly things. I'm not dissing those kinds of cities because of course there will be fun things to do; it's just not our first choice.