But, being an indecisive git, I have no idea which of his books to start on. Do any of his fans out there have a recommendation for me?

Fight Club, most definitely. Or Choke. Both of those are really good. I like Fight Club more, just because I fell in love with the movie version, but Choke is still pretty good. I haven't seen the movie for that one, though.

I would say Fight Club too, since it's so well-known.