I should probably qualify my original post by saying that I don't think I could live on 36K/year in NYC indefinitely. If I didn't have the low-paying job, my runway would disappear in 5-6 months just like the OP. As it stands, I take about $250 out of my runway a month, which means it will last much longer.
I don't really know of "less obvious ways" - what I do seems to me fairly obvious.
1) Rent - I pay $620 a month for a room in Brooklyn that fits my needs in a large apartment where a lot of other people live that's 20 minutes away on the subway from Manhattan (where I would assume the OP works). That's fairly low by anyone's standards, and I intend to keep it that way. I know that if I were to move further out (or, let's say, move out of NYC) I would be able to get a larger place for that kind of money - but the point is that I don't need a larger place, so the "per-square-foot ratio" doesn't bother me at all. I have my own room. Ambient noise coming from the living room or from someone else's room is sometimes an issue (I live with musicians). Earplugs or headphones solve that.
The utilities are split between everyone in the house, the addition is fairly negligible.
1a) This is a somewhat unhelpful generalization, but it has been my experience that someone who was working for a hedge fund in New York is usually not the type of guy that will easily get along with a bunch of pot-smoking musicians that live in a recently gentrified but still somewhat ghetto neighborhood in Brooklyn. However, the OP left and became an entrepreneur, so his soul may still be intact.
2) Food - there was a post sometime ago on how do startups minimize on food expenses. I believe PG's quote was "Rice and beans. There's about 1000 variations".
3) Dating - don't go to expensive restaurants where you are going to lose $150 in one night. A coffee in a local coffee-shop and a walk in the park or on the riverfront - $10, and you are going to have a better time anyway.
4) Sell all your old computer equipment. That old IBM X31 sitting on your bottom shelf that you replaced with the MacBook Pro? You can get around $300 for it on craigslist or ebay.
5) This is an anti-saving tip, but will work in your favor in the end - don't compromise on health insurance.
6) Clothing - I have maybe 2 or 3 outfits that are "date" or "interview" worthy. The rest are crappy t-shirts that I have from college.
There's no silver bullet, to paraphrase Brooks. It's like optimizing your software: you look at what your most expensive expenditures are (profiling) and you try to minimize each one of them in order.