Moving the traversal logic into the application and just sending SQL queries to Postgres (we don't use an ORM) eliminated the lag. RTT between the application and the db was a few ms and this wasn't user-facing logic anyway, so extra latency wasn't an issue in this case.
Probably the fundamental problem here was a sub-optimal schema, but sometimes you're just working with what you've got. Plus a commenter on Reddit pointed out that if we used pure SQL functions instead of PL/pgSQL, we'd also have seen better performance then.