What he did with the NYPD scares me a bit but I think overall he was truly responsible for cleaning up that city (physically). He also implemented the first "Data science" team for a city, which was used to prevent building fires and sewage pipe bursts, among other things [1].
[1]: http://www.nytimes.com/2013/03/24/nyregion/mayor-bloombergs-...