My mental model is that the Fed lends money into existence (either to banks or to the treasury), which creates a loan (that eventually has to be paid back with interest, though I think they can choose not to collect on loans to the treasury?) (I'm also not sure where the money the Fed uses to pay interest on bank reserves comes from, but since it used to not do that I'll ignore it and pretend I'm asking about the time before that existed).

This is true of the Fed's operations in the repo market, but those are a fairly recent development and it's not true in general.

In general, the Fed doesn't lend money into existence, they create money from scratch and then sell that money in exchange for some other asset (typically Treasuries). A bank sells the Fed $1 worth of Treasuries, and the Fed just adds $1 to that bank's account.

However, because the Fed buys a Treasury note/bond in this process, the (rest of the) government then owes the Fed money - i.e. the Treasury note/bond payments. So when the Fed issues a dollar, they also acquire one dollar's worth of somebody else's debt. Note that that's one dollar's worth of debt at current market prices; the Fed will actually be owed more than one dollar. Also, as current market prices shift and the Fed buys and sells assets the amount of money owed to the Fed will generally not be equal to the amount of dollars outstanding.

This suggests that it is not possible, economy-wide, for private sector net savings to increase unless the government debt increases, and that whenever government debt goes down, private savings must decrease.

Private investment is the main thing missing here. Private savings go into a mix of government debt and private capital investments (i.e. grid infrastructure, data infrastructure, railroads, oil wells, real estate, machinery, etc) - i.e. corporate bond/equity-financed capital expenditure. Thus the concern that too much government debt could (at least in theory) crowd out private investments in industry.

As far as I understood money myself, your intuition is correct. All fiat currency are credit money, so that when you are holding a $, either in cash or bank deposit, you are holding someone else liability. The system is balanced, so that total liabilities are equal to total assets at any time. The net value of the entire monetary system in the economy is zero.

That's right, but that's the private sector as a whole. Some part of the private sectors will increase their debt, while others their savings. Clearly that would generate business cycles/boom and bust, and that's the big discussion of macroeconomics in what is the role of governments in damping/preventing them.

Since the Treasury owns the Fed, the profits made by the Fed are channeled back to the Treasury. The ECB is a bit more complex, but it works in a similar way. When a central bank buys government debt, that debt is the facto neutralized.