Okay, Hamilton and Kay were easy. This is the big one. The question, "Which Discworld book should I read first?" strikes fear into the hearts of critics, as there are enormous numbers of variables to take into account here.
First, some statistics. Since 1983 Sir Terry Pratchett has written and published 37 novels in the Discworld setting, combining the adult and YA books into one sequence. The 38th is published at the end of this year, and he is already writing the 39th. There are also four map-books with fictional material by Pratchett in their accompanying booklets, three science books featuring Pratchett-penned fiction interspersed with real scientific observations, two editions of The Discworld Companion, six short stories found in various collections and even a children's picture book. It's quite exhausting to keep track of it all.
The Discworld books themselves comprise a number of continuing characters and ongoing story arcs, although these arcs are mostly relegated to background information (such as Ankh-Morpork gradually evolving from a stereotypical medieval fantasy city into something more Victorian, even steampunk-esque, in the most recent books) or character development (Vimes' evolution from drunken wastrel to a respected commander of the City Watch), with the individual story of each novel resolved in that novel. To add to the confusion, characters from one arc sometimes crop up in others in cameos. For example, the City Watch have their own arc or sub-series, but will generally turn up (to one degree or another) in most books set in Ankh-Morpork, such as a Wizards book, a Rincewind one or one of the Moist von Lipwig novels. There are also some grey areas, such as Monstrous Regiment where Commander Vimes (of the City Watch sub-series) is a prime mover of the plot and action, but only appears briefly.
What follows is a guide to the major sub-series, with the books listed in reading order.
The Colour of Magic, The Light Fantastic, Sourcery, Eric, Interesting Times, The Last Continent, The Last Hero, Unseen Academicals.
Rincewind is a useless wizard, a student at Unseen University in Ankh-Morpork who has no skill with magic (for initially plot-related reasons, but it is later revealed that he is simply inept). Rincewind is the first major protagonist of the Discworld series and is sometimes erroneously claimed to be the main character of the series, despite appearing very infrequently (only twice in the last ten years). Rincewind's primary role is to allow Pratchett to explore remote parts of the Discworld far from the traditional stomping grounds of Ankh-Morpork and Lancre, such as the landmass of XXXX in The Last Continent and the Agatean Empire in Interesting Times. However, as Pratchett's interest in broad parodies has waned in favour of satirical elements, Rincewind, a very broad character lacking depth or much development, has become less interesting and used more infrequently.
The Witches of Lancre
Equal Rites, Wyrd Sisters, Witches Abroad, Lords and Ladies, Maskerade, Carpe Jugulum, The Wee Free Men, A Hat Full of Sky, Wintersmith, I Shall Wear Midnight (rumoured).
The small village of Lancre in the Ramtop Mountains is advised and kept safe by a coven of three witches, Granny Weatherwax, Nanny Ogg and a rotating third member (originally Magrat Garlick, later Agnes Nitt, possibly now Tiffany Aching depending on the next book). Granny Weatherwax is one of Pratchett's strongest and most well-developed characters, challenged in that department only by Sam Vimes. However, recently the Witches have become less frequently used, relegated to supporting characters in the Tiffany Aching YA sub-series. With that sub-series due to close with I Shall Wear Midnight, it will be interesting to see if they return in a main series novel.
Mort, Reaper Man, Soul Music, Hogfather, Thief of Time.
The Death of Discworld was notable for a long time as the only character to appear in every book (even if only for one line), until Pratchett forgot to put him in The Wee Free Men. He has, however, appeared in every book since then. Death is an anthropomorphic personification whose job is to allow the souls of the living to move on to their next life. He usually only manifests during notable or surprising deaths, such as the death of a wizard or witch, not every single death on the planet. Death develops a fascination with humans and their behaviour during the books, sometimes leading to trouble for Death, the Discworld and often both. Death has again become less prevalent in later books, not having his own novel for almost a decade, possibly as Pratchett has exhausted most of the possibilities in Death's character.
The City Watch
Guards! Guards!, Men at Arms, Feet of Clay, Jingo, The Fifth Elephant, The Truth, The Last Hero, Night Watch, Monstrous Regiment, Thud!
The Ankh-Morpork City Watch sub-series is almost certainly the most popular of the various ongoing narratives in the Discworld books. It features the largest cast of them all, many of whom have cameoed in other books set in Ankh-Morpork, and features the most noticeable ongoing development of characters and ideas from book to book, particularly Commander Sam Vimes' evolution from drunkard to respected gentleman. The books featuring the Watch are also generally among the series' best and most acclaimed.
Moist von Lipwig
Going Postal, Making Money, Raising Taxes (forthcoming).
Con artist and scoundrel Moist von Lipwig is saved from certain death by Ankh-Morpork's Patrician, who decides to put him to work as a general troubleshooter to solve the city's problems and repair its institutions. In the first book he takes on the post office, in the second the banking system and in the third it will be taxation. Though a three-book arc has been suggested by Pratchett, some fans believe there is scope for more works, such as one involving the Undertaking (Ankh-Morpork's planned underground rail system) and another about politics, due to the popular fan theory that the Patrician is grooming Moist as his eventual successor. Note that many other recurring Discworld characters, including the Watch, appear in the Lipwig books to various degrees.
Pyramids, Moving Pictures, Small Gods, The Amazing Maurice and His Educated Rodents.
These are books which feature no major recurring characters or elements (aside from the requisite Death cameo) and can be read independently, although it's worth noting that Moving Pictures is set in Ankh-Morpork and features a cross-over with the Unseen University Wizards (who, by some counts, have their own sub-series, but I haven't counted because their appearances cross over with way too many other characters), the City Watch and several other cameos. Small Gods is the best of these and is also the earliest-occurring Discworld novel, taking place between 100 and 200 years before the events of The Colour of Magic.
The obvious solution to the reading order dilemma is to simply start with the first book, The Colour of Magic, and go through the whole series in order. This is easily the simplest solution, but it does have a few issues. The most notable of these is that The Colour of Magic (and, to a lesser extent, the four books that follow it) is written a very different and more simplistic style than the later books and is little more than a fun travelogue and pastiche of various swords and sorcery books, complete with a cameo by characters modelled on Fafhrd and the Grey Mouser and, in The Light Fantastic (the follow-up to The Colour of Magic, the only direct continuation of a primary storyline across books in the whole series), Conan the Barbarian. It doesn't give the best impression of what Pratchett is fully capable of at the very height of his powers.
After this, a solid idea might be to start with the Death sub-series. The first book in the series, Mort, is early enough that it has little to no continuity references and is cited as one of the more popular books in the series (although I only rate it as middling). The problem with this is that the second book, Reaper Man, features an extensive cross-over with the Ankh-Morpork Wizards with multiple references to the events of Moving Pictures and Sourcery, which may confuse readers. Perhaps more acceptable is to start with the City Watch sub-series, which is longer, more compelling and stands alone better.
However, my final conclusion is to go with one of the stand-alones, probably Small Gods or Pyramids, and if you like them to check out The Colour of Magic and take it from there. It's not ideal - both stand-alones are set in remote, never-visited-again parts of the Disc with none of the iconic characters or locations (apart from Death) - but they both give a much better sense of Terry Pratchett's writing style when it's on good form.