(Comments indicated this question was opinion-based, but as it hasn't been closed, I'll self-answer with the results of my research (thanks to commentators for also providing some information) and invite comments or alternative answers if I'm wrong – I haven't read the books, after all.)
First of all, what I called The Book of the New Sun is a series consisting of four books, usually published in two volumes of two books each. It is itself a sub-series of the larger series/cycle called the Solar Cycle, Urth or the Briah Cycle, which is probably what my question should've asked about from the beginning.
The consensus for the best order to read these novels in seems to be in this publication order. However, according to some people you can also start with The Book of the Long Sun; the first quadrilogy The Book of the New Sun can really be read whenever you want, but The Book of the Long Sun must be read before The Book of the Short Sun.
The Urth of the New Sun is a coda/sequel to The Book of the New Sun and should probably be read after that, although some suggest to read it at the very end of the cycle, and others say it's considered optional reading.
There are also several short stories in the cycle, which take place at different points in the chronology. Although these probably could also be read whenever, some of them reference past events and foreshadow future events, so it seems good to read them when they take place in the chronology.
So! Since the consensus for the main novels seems to be to read them in publication order (although I've mentioned some other suggestions above), here's the suggested reading order I've put together, with short stories interspersed chronologically:
- The Book of the New Sun
A tetralogy published as an omnibus called either The Book of the New Sun or Severian of the Guild (UK), separately or in two volumes:
- Shadow & Claw
- The Shadow of the Torturer (1980)
- The Claw of the Conciliator (1980)
- Sword & Citadel
- The Sword of the Lictor (1981)
- The Citadel of the Autarch (1982)
- "The Cat" (1983)
Short story which takes place here chronologically
- "The Map" (1984)
Short story which seems to be an interquel to The Citadel of the Autarch
- The Urth of the New Sun (1987)
A coda/sequel to The Book of the New Sun
- The Book Of The Long Sun
Also sometimes known as Starcrosser's Landfall (early title) or The Book of Silk (in-universe). Another tetralogy, apparently not published as an omnibus, but separately or in two volumes:
- Litany of the Long Sun
- Nightside the Long Sun (1993)
- Lake of the Long Sun (1993)
- Epiphany of the Long Sun
- Caldé of the Long Sun (1994)
- Exodus from the Long Sun (1996)
- The Book of the Short Sun
A trilogy published as an omnibus or separately:
- On Blue's Waters (1999)
- In Green's Jungles (2000)
- Return to the Whorl (2001)
- "The Night Chough" (1998)
A short story set here chronologically.
There are also several other short stories in the cycle that in-universe are fables collected in The book of the Wonders of Urth and Sky, which colloquially is known as the "the brown book". Some are told within the main novels, but others were published later as supplemental material. Since they're not part of the actual cycle, but are meta-fictional, they can probably be read whenever:
- "Empires of Foliage and Flower" (1987)
- "The Boy Who Hooked the Sun" (1985)
- "Folia's Story: The Armiger's Daughter" (1982)
It's also suggested to newcomers to the Solar Cycle that they read Neil Gaiman's How To Read Gene Wolf.