I haven't read any of his books, though I got many recommendations from friends. Which one should I start with? (don't care much about relevance to startup/business, as long as its a good book)
http://www.gladwell.com/archive.html
Gladwell is best taken in small (or at least syncopated) doses, and he really has managed to write about a variety of interesting things. Go find the ketchup essay. It's awesome.
After edit: I say this because I had read many of the primary and secondary sources cited in Gladwell's notes before his book came out. I still learned new facts from his book.