Uncharted Territory
by Connie Willis
4/5 stars because the end worked for me, just barely, and I'm charmed right now, this might go down to 3 stars later. The worldbuilding and its mysteries that are untangled over the course of the book are fucking beautiful. Some of the satire is very questionable, though (poking fun at government bureaucracy is one thing, but the stereotypes applied to the indigenous sentient guide are pretty yikes and insufficiently subverted for my tastes), and I always get surprised how deeply and unshakably heterosexual Willis' outlook is.
Update: Extremely fucking Akiva that I thought about this for 12 hours and realized that (major plot spoiler, seriously, don't read this because the plot is the best part and worth experiencing unspoiled)