If you can think of more cities, let us know.
Denver is blessed with amazing central neighborhoods. I live in a house with a yard and the whole bit. Yet I'm 11 minutes by bus to Downtown. I generally ride my bike to work (we have an amazing intra-city bike path system) or take the bus. Because Denver is so incredibly compact getting around without a car is easy.
Our neighborhood has lots and lots of restaurants, coffee shops, dry cleaners, etc... so we almost always walk when we go out.
Point being: Denver certainly fits the bill.
It's also rather affordable. I'm a huge fan:)
They are small in proportion to the overall populations of the respective cities' urban areas, but that's almost entirely because public transportation has lagged the construction of suburbs and sprawl. Boston's T, or Philly's SEPTA were mostly constructed in the early 20th century so it's only those older areas that are feasible for car-free living. (The DC Metro is an interesting exception in that it's a much newer system, but it too fell out of step with development.)
In fact, I'd say that there's a sort of "car free radius" that's basically the edge of residential areas just before World War II. The suburbs that got built after that are hugely car-centric, ones built before typically aren't.
Also, there is a spectrum from being totally car-dependent to not owning a car. My parents live in the D.C. suburbs and they have more cars in their garage than people who live there. Because you can't even go to the drug store without driving several miles (and this isn't a far-flung exurb, they're only 17 miles from downtown) my brother and I each got a car as soon as we could drive. Meanwhile, I now live in Westchester (a suburb of NYC), and while I own a car I only drive it a couple of times a month (Costco trips mostly). The same is true for Chicago. Unlike in Manhattan, most people do own cars, but a large number of people don't use them that heavily because the suburbs are easily accessible by train.
From my experience I would say only the top 7 on the above list are fit for life without a car. Can't imagine not having a car living in Miami or Minneapolis.
full disclosure: I've lived in NYC without a car for 10 years, but grew up in Ohio completely car-dependent.
Edit: There are in fact many places that do meet the requirements of affordable and walkable, but a new concern in an age of urbanization is keeping them affordable. The desire for such neighborhoods is growing, but the supply is too low as of 2013.
Although being a single guy here, I think women see it as a red flag (at least from what I see on okcupid). Interested in moving to NYC unless I find somewhere cheaper and still interesting.