So no real threat from Russia was expected at that time.
Governments can change. This issue was mentioned as such in this regard by [then Deputy Secretary of State] Strobe Talbott, in 1995:
among the contingencies for which NATO must be prepared is that Russia will abandon democracy and return to the threatening patterns of international behavior that have sometimes characterized its history, particularly during the Soviet period.
I remember the West being freaked out by Zyuganov possibly winning the elections in the 1990s, for instance. At least nowadays, there's hardly any difference between Zyuganov's positions and Putin's, when it comes to foreign affairs, so those fears were probably not entirely unjustified. Also, an internal 1996 document of the CPRF shows that they were actively focusing on attracting the nationalist [Zhirinovsy camp] votes, even back then. This is one of the reasons why he ran as a candidate of the Bloc of National-Patriotic Forces of Russia, instead of the CPRF. And more explicitly:
Zyuganov platform was also composed with the nationalist voters in mind. Even though the
communists were by far the most dominant force within the alliance, nationalist themes
dominated its program. It elaborated in great detail all the key ideas the Russian nationalists had
been articulating for years. [...] It accused Yeltsin of the destruction of the USSR and
the abandonment 25 million of ethnic Russians in the former Soviet republics. The platform
promised to the restore territorial integrity of the former Soviet state, regain it former
superpower status, recreate a strong military, and abrogate those international treaties which undermined Russian national interests (Zyuganov, 1996a).
And (I recall) the West turning a (relatively) blind eye to Yeltsin less than democratic means of subduing the parliamentary opposition for that very reason. Etc. Russia was never really convincing as having abandoned its Soviet ways completely, to quite a number of observers, particularly those from Eastern European countries. Their cooperation with the West on Yugoslavia was doubled by attempts to subvert the process too--Russian paratroopers on Pristina airport etc. Despite the Russian rhetoric on NATO expansion as if it happens by some centralized force, those Eastern European countries all applied to join, just in case the wind started to blow in a different direction in Moscow. E.g.
“When we were a candidate country, I often heard the phrase: ‘Russia is not going to be happy if the Baltic countries become members of NATO,’” said former PresidentVaira Vike-Freiberga of Latvia, another woman who, like [M.] Albright, had her perspectives on foreign policy shaped by experiences as a World War II refugee. Often standing out as one of the only women in the room, Vike-Freiberga led her country to NATO accession in 2004 as Putin was consolidating his power across the border. “President [Jacques] Chirac of France told me: ‘You should not be fooling with the mustache of the bear, you shouldn’t annoy him.’ I said, ‘No, Mr. President, but we do not want to be eaten by the bear, either.’ That is the point.”
And if you want to go back to Poland's  NATO admission speech, their position (as exemplified here by their MFA Bronislaw Geremek) was not that different, albeit the threat of external force was only mentioned in historical, but rather concrete terms...
For the people of Poland, the Cold War, which forcibly excluded our country from the West, ends with our entry to NATO. Poland, as member of the most powerful alliance, bringing together democratic nations of Western Europe and North America, joins the vital process of bridging old divisions and contributes to the security and stability in Europe. [...]
The nations, who join this community today, were denied those values until 1989. On the streets of Budapest in 1956, Prague in 1968 and Gdansk in 1970 and 1981 they paid a heavy price. They have proved their democratic credentials, which give them the right to be here today.
Why the West agreed is a somewhat different question, which is honestly a bit difficult to retell concisely. In Bush's time, when the major expansion happened, he was hemmed in by Iraq war policy and looking for allies beyond the traditional Western Europe which wasn't all that supportive (see the fabled "you forgot Poland" in the Bush-Kerry presidential debate). That stuff has been derided, but there have been more serious US positions around that time why the US wanted allies further east.
As for the Western EU capitals, I think it would have been politically difficult for them to agree to expanding the EU but to oppose expanding NATO, especially since the EU treaty has a common defense clause too. Such a stance would have probably come across as naked anti-Americanism. Even though some German press declared Poland a "nation of thieves" and a Trojan horse of the US with respect to Iraq... But that only emphasizes why these Eastern European countries saw the US [and thus NATO] as the true guarantor of their security. The Western Europeans were seen as less reliable and possibly even conflicted on economic matters, like Russian gas etc.
And looking back at one of Albright's speeches (from 1997) that angle (of US being the real deal in terms of security guarantees) is emphasized, albeit to a US audience:
Many organizations are doing their part to assure the prosperity and security of Europe. The European Union is expanding. The OSCE is promoting democracy and helping to resolve conflicts from the Caucasus to the Balkans. Many of the new market democracies are joining the World Trade Organization and the OECD.
But NATO is taking the lead, just as it has for the past half century. NATO is still the anchor of our engagement in Europe, the only organization in Europe with real military might, the only one capable of providing the confidence and security upon which our other goals depend.
One other worthwhile point she brings up is that during the process/negotiations of joining candidate countries were more or less compelled to solve many/most of the their outstanding issues... peacefully.
Just the prospect of enlargement has given central and eastern Europe greater stability than it has seen in this century. Old disputes between Poland and Lithuania, Poland and Ukraine, Hungary and Romania, Italy and Slovenia, Germany and the Czech Republic are melting away as nations align themselves with NATO. Democratic reforms are advancing. Country after country has made sure soldiers take orders from civilians. These nations are fixing exactly the problems that could have led to future Bosnias.
And finally, she does get to the "historical injustice" angle that we saw in the Polish speech too, albeit this just the third leg of her argument to a US audience.
The third reason, Mr. Chairman, as I suggested, is to right the wrongs of the past. If we don't enlarge NATO, we will be validating the dividing line Stalin imposed in 1945 and that two generations of Americans and Europeans fought to overcome. That's conscionable. With the Cold War over, there is no moral or strategic basis for saying to the American people: "we must be allied with Europe's old democracies forever, but with Europe's new democracies never."
We would begin to think in entirely new terms about what a European continent, whole and free, would look like, and what our relationship with Russia and other key states on such a continent would be.
And the Clinton-Yeltsin discussion in the Kremlin from May 10, 1995 is actually not too far from a combination of the above: Clinton promises (p. 7) that Russia won't be excluded from consideration for NATO membership (at some point), but invites Russia to sign the Partnership for Peace first and consider a "special relationship" (which I'm guessing later became the 1997 agreement). Yeltsin asks for any NATO expansion to be postponed preferably until 2000, but at least for two years. Clinton then lays out his reasons for NATO expansion.
WJC: Our goal is for the U.S. to stay in Europe and promote a unified, integrated Europe. I propose the following:
[...] that there be a role for Russia in PFP and a clear statement from the U.S. that Russia should not be excluded from NATO membership. [...] But you have to walk through the doors that we open for you. That's why I've urged you to sign the,PFP documents and launch the NATO-Russia dialogue.
Clinton also mentioned a "post-COCOM" deal and G-7 membership (i.e. dangles some carrots) in the context of "greater integration of Russia into other international institutions".
BNY: [After a long pause] But, Bill, what is involved here besides a a strategic issue is that there's an overlay of political problems~-this year the parliamentary elections, next year the presidential ones. One false move now could ruin everything. So please postpone this issue--if not until 2000, then at least for the next few-years until you and I get through our elections--so that there is only theoretical discussion about expansion. Then we can explain all this to the Eastern Europeans and the Central Europeans; we'll tell them that the time will come for expansion later.
I've got to tell you, my position heading into the 1996 elections is not exactly brilliant. [...] But let's postpone NATO expansion for a year and a half or two years. There's no need to rile the situation up before the elections. [...]
WJC: But you've raised political forces, so let's talk about those. You described what you are facing in 1996. Let me tell you about my situation. I face a difficult campaign, but I have a reasonable chance. The Republicans are pushing NATO expansion. Wisconsin, Illinois and Ohio are key; they represented a big part of my majority last time --states where I won by a narrow margin. The Republicans think they can take away those states by playing on the idea of NATO expansion. [...] You can say you don't want it speeded up --I've told you we're not going to do that --but don't ask us to slow down either, or we'll just have to keep saying no.
So yeah, Clinton played his own domestic elections card here (in return). But then gets to the Albright-y/Talbott-y stuff:
There's a third factor. The truth is·that for the people in the Central European countries who most want to be in NATO, it's part of being accepted by the West. But they also have security concerns. That's where it gets complicated. They trust you, Boris. They know it would be inconsistent with your interests for them to be in NATO overnight. But they are not so sure what's going to happen in Russia if you're not around, so they're conflicted: on the one hand, they want to be in NATO in a hurry, but on the other they also want you to succeed with reform and don't want anything to happen that will prevent you from doing so.
Clinton the eggs/invites Yeltsin several more times during the conversation to join the PFP. After a break (in which he says he talked to Chernomyrdin), Yeltsin agrees (p. 12). Then he brings up G-7 cum G-8. Clinton promises to immediately talk to Kohl about it. Yeltsin then asks about FBI help with explosives tracing in re Chechnya and the like, Clinton again promises to help. Yeltsin then asks about CIS. Clinton says nobody in his administration will oppose it in any way as long membership is genuinely voluntary. Then they start to talk about COCOM relaxation; Clinton promises to make Russia a "full member" of COCOM by 1999, but also asks that in return for Russia cut off arm sales to Iran. So it is somewhat clear that the agreement was part of "package deal", even though neither side is too openly transactional about it. Towards the end of the conversation Clinton repeats a couple of times his sales pitch about NATO expansion being a "slow, gradual, deliberate protess, consistent·with the goal of an undivided Europe" ... "and enhancing the security of all parties, including Russia". In a later brief conversation in the Hall of Facets, Clinton reminds Yeltsin than it's important for [FM] Kozyrev to sign the PFP by the next NATO meeting, so that he can deprive Bob Dole [back in Washington] of much discussion on alternative approaches, by presenting a done deal.
And I think it's a bit of a misconception that NATO was all that expansionist during Clinton's time alone. I vaguely recall more countries having applied back then, but not being quite so welcomed. For example Romania was sort of put on a waiting list:
July 1997 - NATO holds its "enlargement" summit in Madrid; the Alliance decides to invite the Czech Republic, Hungary and Poland to join the Alliance; the final communiqué confirms that the process of enlargement continues; the text nominates Romania among the candidate countries which have made significant progress in fulfilling the NATO membership criteria.
Romania and six other countries joined during Bush's presidency, i.e. in 2004. Only three countries joined during Clinton's. I haven't quite summed up the areas of the 1999 vs 2004 waves, but on first glance they look similar.
I also think it was not all that
clear that extending NATO would change the situation and bring back the confrontation
(as the question says) because Russia and NATO back in 1996-97 had agreed to the “Founding Act" (on Mutual Relations, Cooperation and Security between NATO and the Russian Federation signed in Paris), in which NATO countries promised not to deploy nuclear weapons or "permanent stationing of substantial combat forces" in the new NATO members.
Eventually, those NATO promises became insufficient for subsequent Russian governments (specifically Putin's--he demanded a rollback to a pre-1997 situation sometime in late 2021). But it was hardly clear to participants in the 1997 agreement that those restrictions on NATO force deployments would be seen as insufficient (much) later by a subsequent Russian governments.
It's true however that even Yeltsin equivocated on NATO expansion, changing his level of stated opposition. In particular, the issue was electorally toxic for him back home. So, the Clinton administration postponed any concrete steps until after the 1996 election in Russia. On other hand, even Yeltsin recognized [e.g. to Clinton at Hyde Park in 1995] that the Polish American Congress was exercising pressure in the opposite direction in the US elections. I recall one Canadian diplomat claiming to me that this was a major factor in US support, but that kind of claim is somewhat hard to substantiate. But one book kind of supports that:
Of the ten districts with the highest concentration of Polish Americans, Ronald Reagan had won seven in 1980 and nine in 1984. Although [H. W.] Bush also won nine of these in his race with Michael Dukakis in 1988, Clinton had take seven of these districts in the 1992 campaign. (And he would go on to defeat Bob Dole in eight of them.)
Somewhat counterbalancing that though:
A poll taken in 1996 showed that while Americans of central and eastern European descent did not show support for NATO enlargement at higher levels than other Americans (who were generally favorable), they felt more strongly about the issue and they were also significantly more likely to be aware of it.
The book also recounts how Bob Dole's tried to court that vote by "naming [country] names and setting a date" for the enlargement, and meeting with Lech Walesa. So, yeah, there was the US domestic lobbying aspect at least for Poland, but it's probably hard to pin too much on that angle for the other countries that joined (later or in the same wave). It's also worth noting that not all Republicans tried to "one up" Clinton on this. And neither were all Democrats convinced. Sam Nunn opposed "rapid NATO enlargement" for fear of jeopardizing nuclear disarmament agreements with Russia, and voted against one relevant bill, somewhat famously changing his vote to nay during the roll call.
Support for enlargement was ultimately a fairly broad affair in 1997-98 (vote was 80-19 in the Senate, with 67 required to pass):
Although support for NATO’s enlargement was broad, it was comprised of what political scientist George Grayson later called a “strange bedfellows” coalition, including Republicans and Democrats, defense hawks and human rights idealists, unionists focused on the brave actions of Poland’s Solidarity, and business leaders focused on the lure of new markets in Central Europe.
The people entrusted with making this law pass the Senate were also tasked to convince that it would
not come at the expense of other U.S. interests, including constructive relations with Russia. Clinton had staked a good deal on building closer ties to Russia and President Boris Yeltsin. A win on NATO enlargement would be undermined if pursued in a way that needlessly poisoned that relationship.
And in particular:
The [NATO-Russia] Founding Act was positive enough toward Moscow that it reduced anxieties (mostly among Democrats) that NATO enlargement would antagonize Moscow. But it also had enough red lines between Russia and NATO’s own decision-making that it minimized concerns (mostly among Republicans) that NATO was giving Russia any kind of vote or veto.
So back then (late 1990s), in the US at least, the expansion was not seen a posing that kind of "clear" danger (by most US decision-makers), given these other mitigating efforts the US/NATO was undertaking vis-a-vis of Russia.
What I personally find more surprising is that the second, 2004 expansion was voted 96-0 in the US Senate, despite involving more countries that were closer to Russia, and which had longer borders with it, than in the 1999 wave. Pretty much every article I've read on that latter vote mentions that a number of those countries stood by the US on the Iraq decision... and some of the new candidates had helped the US logistically or militarily (e.g. Romania and Bulgaria). Unfortunately, it is difficult to research whether the amount of verbal opposition/protest from Russia's leadership against NATO expansion had gone up or down in that 1999-2003 time frame. For what it's worth, the NYT wrote in their 2003 coverage of that Senate vote:
But past Russian opposition to NATO expansion has faded under President Vladimir V. Putin, who has carved out for his country a consultative role with the alliance.
So, at least some of the US opinion makers were of that view. (And the consultative thing seems to refer to the 2002-established NATO-Russia Council.)