Given a region in a city, I'd like to make a list of all the street addresses it contains in an order which is reasonably efficient for a person to traverse on foot. Ideally, I'd like the solution to use free software. An optimized set of lists for multiple people to traverse simultaneously would be even better. Does this already exist?
This is the travelling salesman problem, although I'm not sure that you care about returning to the same place as you began. The TSP is NP-Hard: for even a small number of destinations to be visited, there is an incredibly large number of possibilities for an algorithm to consider before it can tell you what the optimal path is. I haven't tried with every street address in a city, but I imagine it would take a long time to come to something resembling a good answer. I would reduce the number of possible solutions by reducing your destinations to street segments, rather than addresses.
A free and open source implementation exists in pgRouting:
Unfortunately I'm not sure about the multiple people aspect, but if you have districts or obvious geographic barriers that are hard to pass on foot (e.g. a train line or a motorway), then you could try get one solution per 'district'. This has the additional benefit of reducing the solution space further (this may not be a benefit if accuracy is more important than having a fast algorithm).