I’m glad I started with Going Postal, and I am just not sure if I would have given Pratchett another chance had I started with The Colour of Magic. My second read was Thud!, and I do wish I’d have read other Vimes books before I had read that one. Nevertheless, I think starting with a later book, where Pratchett shows improved storytelling, may be better than starting at the beginning.
I’m no expert though. I’ve finished a little under half of the Discworld books, as well as Nation, and I’ve done a lot of jumping around. When picking a new Discworld book it is hard for me to go back to the earlier novels because they are far inferior in quality than the later books in my opinion. Right now I am about a third of the way through Small Gods. I chose it solely because of the high ranks it got in the Discworld poll thread a while back. So far it is only so-so. Well, it is really good, but so-so compared to other Pratchett books, imo.
For me the best* is Going Postal, followed by Making Money, followed by the Vimes (City watch) series. The Wizards just don’t stand up in terms of quality for me.
*Excepting the Tiffany Aching series, which is the second best fantasy series written, second only to The Lord of the Rings.