Start with The Third Man. It is barely a hundred pages, Greene wrote it as a treatment before the film rather than as a novel, and it is the fastest possible demonstration of what he does: a decent man in a ruined city discovering that his friend is a monster and that the choice in front of him has no clean side.
If you want a full-length novel first, make it Our Man in Havana, a comedy about a vacuum cleaner salesman who invents an intelligence network and is believed. It is very funny and it is also a serious book about how institutions consume fiction they want to be true. Either of these beats starting with the Catholic novels, which are the deepest Greene and the least welcoming.
The entertainments
Greene divided his own work into entertainments and novels, and largely stopped doing so later, but the split is still the most useful map. Read The Third Man, then Our Man in Havana, then The Human Factor.
The Human Factor is a late book and the best spy novel he wrote — quiet, domestic, devastating about loyalty. It is also the one that most clearly shows the entertainments and the serious novels were never really separate categories.
The great political novels
The Quiet American is the single best Greene and the one to read third or fourth, once you know the voice. Its portrait of a well-meaning American idealist causing carnage in Indochina was published in 1955 and has not needed updating since. If you only ever read one Greene, this is the argument for making it this one rather than the famous Catholic titles.
Then The Comedians, set in Haiti under Duvalier, and The Honorary Consul, set on the Argentine border. Both are late, both are exceptionally well made, and both are about the same recurring Greene figure: the burnt-out foreigner who discovers he still has one commitment left.
The Catholic novels
Brighton rock, The Power and the Glory and The heart of the matter are the books his reputation was built on, and they are the ones a modern reader most often bounces off.
The obstacle is real and worth naming. These novels assume that damnation is a live possibility with concrete stakes; the plots turn on mortal sin, on the difference between a bad man and a damned one, on whether a suicide can be forgiven. If those propositions are inert for you, The heart of the matter in particular can feel like a tragedy about an accounting error. Greene himself grew impatient with the "Catholic novelist" label and said the religion was material, not doctrine.
Read The Power and the Glory first of the three — the whisky priest fleeing through anticlerical Mexico is the most human of them and the least theological in its machinery. Brighton rock is the most brutal and has the better prose. The heart of the matter is the most divisive.
Where to stop
Four books gets you the real Greene: The Third Man, Our Man in Havana, The Quiet American and The Power and the Glory. Add The Human Factor if the spy side appeals, and Brighton rock if the moral side does. There are roughly twenty more novels beyond this list, and diminishing returns set in faster than his admirers admit.
For other twentieth-century novelists in the same register, see William Faulkner.
Follow the full ordered path here: Graham Greene Reading Order: Where to Start.