Good Omens is a great place to start with Pratchett, it's by both him and Gaiman but the writing's pretty clearly Pratchett's.

If you want to go right ahead into the Discworld books, I'd actually suggest first doing something more recent and then backtracking to the earlier stuff. Going Postal, maybe, it's a pretty good stand-alone.