I started with Color of Magic, but didn't really get into it much. It was fine writing, but nothing very special. Then I read some later works and realised that he got much better.

I went to a talk by Pratchett and he pretty much admitted the same thing. He suggested starting with book 6 or so. :)