Start with his short stories. One of the best, and one of my favorite stories by any author, is "A Little Fable": http://www.flashfictiononline.com/fpublic0012-a-little-fable...

Then, perhaps, "The Metamorphosis", before or after reading Nabokov's lecture on it.