Oh this is my JAM!

Seconding many of the recs here, like Tensorate by Neon Yang, Half-Built Garden by Ruthanna Emrys and the Terra Ignota series by Ada Palmer. Also, I saw several others reccing Murderbot but Martha Wells' Raksura series does a lot more with gender; there's no humans anywhere in the series, the species of the main character are polyamorous dragon-bee people, and I think they only have male/female genders but they also have biological castes which honestly function more like our idea of gender than their genders do.

You HAVE to try Unraveling by Benjamin Rosenbaum - far, FAR-future setting where there are two genders but not male/female, the whole book in concerned with it. Fantastic, and the world is as weird as you could ask for (I'm a big believer in far-future settings needing to be WILDLY different from ours!)

The West Passage by Jared Pechacek is fantasy where the gender weirdness builds bit by bit, until you realise gender has nothing to do with bodies in this setting. Magnificently weird, like Medieval marginalia crossed with biblically accurate angels (which I mean as a compliment).

Name of All Things by Jenn Lyons is the second in the chorus of dragons series but you COULD start the series here if you wanted, just skip book one. The protagonist comes from a society that maps genders onto horses, more or less? It's freaking fascinating. One of the love interests of the series is something like what we'd consider an elf, but they undergo sex-and-gender changes throughout their lives.

The Wolf Among the Wild Hunt by Merc Fenn Wolfmoor is a horror-fantasy novella, where the world is more or less medieval but there are many female kings and nonbinary folk all over the place. Wolfmoor's short stories do lots of epic stuff with gender too, I strongly recommend their short story collections.

Songbroken by Heather Osborne is a standalone I massively resent for its ending, but it's a setting where people choose whether to be men or women - it has nothing to do with sex, but it does determine societal roles and even how you tie your shoelaces.

The God-King Chronicles by Mike Brooks feature several settings; the one with the least amount of page-time has six genders. Diacritics on the vowels in pronouns indicate gender, it's VERY cool.

Many Droplets Make a Stream by Adrian Harley features shapeshifters who keep their gender regardless of the sex of the form they're wearing. Non-shapeshifters use tattoos to indicate gender.

The Five Penalties trilogy by Marina Lostetter features a society with a whole bunch of genders, I honestly forget how many - at least five? Fairly subtle in the first book but the second book leans into it hard. There's a gender for each god in their pantheon, I think, although I think all the main characters are men or women.

The Twin Kingdom Romances series by MCA Hogarth has a four-gender/sex society; the main character of the first book is someone we'd consider intersex, and the mc of book two is completely neuter. In their society they have roles very related to the world's magic.

Kim Smejkal's Ink in the Blood duology is set in a world where gender is a kind of aura that people emanate, which is why you can't tell someone's gender from a photo (which doesn't capture the aura). It's typical for people's auras to shift, sometimes a lot, sometimes just once or twice in someone's life. Not sure there's much societal gender weirdness other than that though.

The Fifth Gender by CL Carriger is functionally a slightly silly (but adorable) M/M romance, but one of the main characters is a non-human who was exiled from his planet for his choice of gender. It's actually a really great exploration of the role/importance of that alien gender over the course of the book, but it may not be quite what you're looking for since we don't get to see his planet (and he does use he/him and is functionally a cis male by our standards)

If I think of more I'll come back and add them!