I probably *wouldn't* start with _Colour of Magic_. It's rather different from the rest of the series, being a Fritz Leiber parody, and his style only starts to gel a few books later on.
My recommendations? _Small Gods_, which a minister once described to me as the best book about religion he'd ever read. _Pyramids_, which is about fate, belief (not the same as religion!) and camels. _Mort_, about growing up, death, and Death.