Or second, since I read Good Omens yonks ago.
Small Gods is a safe start – it’s funny, insightful, and guaranteed to stand on its own, so you don’t need any backstory to enjoy it.
Of course, since you already enjoyed Good Omens (or so it’s implied), you shouldn’t have a problem with Pratchett’s solo stuff. By most accounts, he did the bulk of the writing on that book, too (since Neil was busy doing comic-book stuff at the time).
I second Small Gods as a good place to start. There are many preferences among dopers and other fans which series is the best, I don’t agree, because I really like the wizards and wizzard, but the majority seem to think that the Watch series is the best, so it should be read in order. There are some cameos, which might be a little hard to get when you read the books out of publishing order, but check out the L-space web for good cross references and annotations. They’re lagging a bit with the newer books, but it’s still the best resource on the net, I think.
Small Gods is one of my favorites, too, although it doesn’t have many of the Discworld “regulars.”
I started with Reaper Man or Mort which introduce Death as a major character. You might enjoy that, since he makes an appearance in Good Omens as well. Discworld’s Death is more of a fun guy, though.
The Ankh-Morpork Night Watch is probably the most fully-develop set of characters, though. Guards! Guards! is the first in that series and quite good, although not as complex as the late Night Watch books.
I disagree…I think **Small Gods ** is a bit too complex for an intro to the Disc. I’d recommend either **Wyrd Sisters ** or **Guards! Guards! ** as an intro. Then you can follow the mini-arc of each. Or start with Mort and do the Death books. Or you can do the stand-alones Pyramids and Moving Pictures. Or you can…
For any given Pratchett fan, there are at least three starting points. 
I disagree with your disagreement. Small Gods was the first Discworld novel I ever read, and I was pretty much a lifelong Pratchett fan by around page ten or so. It’s still my favorite, although not without close and heated competition.
Honestly, though, it doesn’t really matter what order you read them in, even the ones that are part of a larger arc. All of the novels are stand-alone stories with no previous knowledge of the setting or the characters required. You’ll miss out on some of the running gags and subtler complexities of character relationships, but that’s just an excuse (as if you’d need one) to go back and re-read the books later.
I think Guards! Guards! is a great place to start, both because it starts at the beginning of the guards’ arc, and because it’s a heck of a funny book. I was laughing hard before I’d finished the dedication and made it to the first chapter.
I wouldn’t start with Wyrd Sisters unless you know your Shakespere. I never really read it so I didn’t get a lot of the jokes until I read the annotations.
Although there is some overlapping, there are certain themes to some of the different series. People tend to enjoy the books that parody things they know more about.
The Witch books tend to parody literature (Shakespere, The Phantom of the Opera, Dracula).
While the Rincewind books start out by parodying literature (Faust and various fantasies), later they tend to parody cultures (Asian, Australian).
The Watch books are big on detective fiction while also bringing in a lot of real world events (the Kennedy assasination, that island in that rises above the water that I can’t remember the name of).
The Death books seem to be more diverse, a couple of them aren’t even really parodies.
I’m gonna go out on a limb and suggest you start with the first two books. The Colour of Magic and The Light Fantastic. While they’re not the most well written, (Terry hadn’t really found his style yet) they are amusing and they give you the best first look at the Discworld.
I sent a friend Small Gods and Guards! Guards! for Christmas. Either one would be a great choice.
I started with Guards! Guards! and it left me a hopeless Discworld addict. I’d definately recommend it, because of all the reasons previously mentioned. Wyrd Sisters and Mort are also good if you want to get into reading their mini-arcs, and The Truth and Small Gods are my favorite stand alone books. I wouldn’t recommend starting at the beginning of the series, since the first few books have rather weak material compared to the later ones.
I think Mort or Reaper Man is a good choice. As far as I can tell so far, Death is the only character that shows up in every book, so it helps smooth over the confusion a little bit when you’re reading along and suddenly see someone SPEAKING IN ALL CAPITALS and it takes a moment to put together exactly what just happened.
Other than that, I agree with what Miller said – the books are all pretty stand-alone. Reading them “in order” will give little nuances and help you make connections more quickly, but it’s not essential.
IIRC, Reaper Man was the first that I ever read, but I’d already forgotten pretty much everything about it before I started reading them again.
The first one I read that started me on my latest kick was Night Watch, and it remains my favorite. It makes reference to a ton of stuff that’s happened in earlier books, but it’s actually kind of fun to work my way backwards through the series. It’s kind of like reading two books at once; whenever I read one of the other books I can say, “Oh, so that’s why that character in Night Watch said that…”
Ok, it depends on what you like, I would say.
A very brief synopsis: The Guards series, which starts with Guards! Guards! is focused primarily on Ankh-Morpork and even more so on one individual who is a lot like a *much * cooler combination of John Wayne & Clint Eastwood. Did I mention he’s cooler than both?
The Witches series is…well…about Witches. I can’t tell you much, because I don’t like them, but from the couple I did read, it’s about three distinctly different personality types all trying to get along. I believe the first book is…oh, damn. Some help here?
The Rincewind series is about one inept wizzard, or so he calls himself. It’s fairly witty and quick but doesn’t appeal to everyone, I think because of Rincewind himself. I think this starts either on the **Colour of Magic ** or the Light fantastic, I can’t remember which is the first one.
And then there’s his other books. Mort & the Grim Reaper are excellent books, but the whole Mort series went rapidly downhill (IMO) with the introduction of Susan Sto-Helit, a mean little bitch if I ever saw one. 
But again, this is only opinion. These books center around the difficulty of being an fictitious persona in a real world. The series starts with Mort, I believe.
Good luck and I hope you enjoy it. Come back and chat about it when you read some.
Oh I wanted to add: while the Truth was just OK to me (chiefly because I did no like ONE BIT the way the guy was uppity to Vimes), Monstrous Regiment was decent and Going Postal was excellent. Me and the SO both read it twice, and he rarely re-reads books.
Hush your mouth. You’re talking about the mean little bitch I love.
I wouldn’t worry too much. I started on The Last Continent, not one I’d recommend to start with, but it was so damn funny I was hooked anyway.
I’ve identified another arc, of books providing Ankh-Moorpork all the modern conveniences. These are Soul Music, Moving Pictures, the Truth, and the recent Going Postal (which is excellent, by the way.) Monstrous Regiment is pretty much standalone, but I was disappointed in it.
The first Witches book is, technically, Equal Rites, as Granny Weatherwax is a major character in it. None of the others appears, though, so the first real Witches book is Wyrd Sisters.
Yeah I kind of figured someone would come along to defend Susan shortly. She is like that - you either love her or hate her.
Monstrous Regiment - the sergeant reallywon me over. I liked him a lot.
I’d also add that, if you do get into this, don’t neglect his “children’s” Discworld books: Wee Free Men, A Hat Full of Sky, and The Amazing Maurice and His Educated Rodents. They are every bit as good as the adult series. They are fairly stand-alone, although I think the first two are better if you have some of the Witches series under your belt first.
I don’t understand why so many people like Vimes as a character so much.
I really don’t like him, and the City Watch books are my least favourite because of that.
I think the Tiffany Aching books may eventually supplant the Watch books as my favorite DiscWorld arc. Hatful of Sky really impressed me. It’s basically a children’s book about euthanasia. How cool is that?
Pterry’s books generally are based on a set of characters. The ones that I can think of are the Guards, the Witches, Death (and family), Rincewind, and then there are some that don’t quite fit in. Some examples are Small Gods, Pyramids, Moving Pictures, the Truth, Monstrous Regiment, and Going Postal. You should read the theme books in order and the non-related ones afterward (in my opinion).
Somewhere on the L-space webpage is a guide for reading order. I don’t really believe that there should be any orthodoxy; read them for fun, but in the set books, you get more out of the read by doing them on order.
I did a quick search, but couldn’t find the guide. Feel free to spend the better part of a work day at l-space.
http://www.ie.lspace.org/
I think Pterry thinks that they should be taken lightly as well. I met someone (10+ years ago) who said the his books changed their life. I looked at them in a funny fashion. There are some spiritual messages (Feet of Clay, Small Gods, Carpe Jungulaum) but these are more an exception than the rule.