Ok, as a Russian, I have some thoughts on it:
1) The first thing is to have the USSR intact and managing to bargain the "Finlandization" of Eastern (or the entire) Europe from the West. It was already mentioned here, that even if the so-called "Informal Bush senior promise" had existed, it was completely dead after the Union's dissolution (it's a fun thing that the end of the Cold War was declared by Bush senior and Gorby during the Malta summit, while nowadays everyone think that it came onlly after the complete Soviet collapse in 1991). So, having a stronger Moscow (which still maintains reasonable level of relations with the West, ofc) would be really helpful. The propositions to Finlandize Eastern or the entire Europe were floating around since late Cold War and seemed to be the logical end game of the Soviet detente started during the Brezhnev Era (although, the first such proposals from Moscow is the Stalin's Note on Germany). In order to achieve that, you may play with some PoDs in around 60s-80s, which would make the US weaker/less hawkish (thus more willing to make a deal with the Kremlin) and/or making the USSR stronger, with earlier and more sensible reforms (while keeping at least Brezhnev pre-Afghan level of US-USSR tensions).
2) The second thing is to make the US more intrested in Russia during the 90s. The thing is that the first foreign minister of Russian Federation, Andrey Kozyrev, really hoped that the US would provide a "Second Marshall plan" for Russia, thus providing many concessions in order to boost the image of Russia in the West (for example, making the process of Russian troops withdrowal from Baltics b5 years faster than initially planned- setting up 1993 as the year for all Russian military to witdraw instead of 1998). For that we could use the Ross Perot victory in 1992 (the guy was very Anti-Chinese and wante to make Russia into "Citael of democracy"). And 1993 WTC bombing succeeding would be a good PoD too- with War on Terror strating 8 years earlier, the US would be too occupied with islamic terrorists to intervene in Yugoslavia (and the Bosniaks wouldn't receive the US backing dur to the earlier rise of islamophobia). The First Chechen War is easier to win for Russia with better PR (while the Chechen leadership during the First War, unlike the Second, used to be secular nationalists, it's easy for propaganda to play on the islamophobic themes). So, with Muslims being the "common enemy" for both Americans and Russians during the 90s, we may see much less strains in US-RF relations.
3) Chernomyrdin succeeding Yeltsin. Basically, Viktor Chernomyrdin was a long-serving premier, who'd initially been chosen as a compromise candidate to replace Gaidar in 1992. Basically, I came up with that idea due to the Gore-Chernomyrdin comission. Let's say that in US Gore is also elected in 2000 and the two develop an early Putin-Bush junior kind of relations with each other. Under Chernomyrdin, Russia may become a something like "Giant Ukraine"- a country run by Oligarchs without a stongman-ish leader like Putin. So, there is no "restoration of pride" in early 2000s Russia, the aftershocks of the 90s (gangs) last a bit longer- but Russia still looks as humilated as during the 90s, so there is less reasons for the Eastern Europeans to distrust her (although their fears of Russia have roots deep in history, so they would likely call for further "containment" no matter what).
4) Harliner China? Basically, with no Deng and his "Reforms and opening up", China would likely stay Maoist in some form (Guodeng or Gang of 4). So, USSR/Russia in such timeline may receive more Western investment and, with the PRC becoming the leader of the communist world after the USSR dissolves/reforms, we may see Western attention being directed towards China- especially if the continued backing of the Naxalites, Shining Path and Filipino communist guerillas would result in actual Civil Wars. So, with China being a common enemy for Washington and Moscow, the NATO expansion becomes less likely with Finlandization being more seriously considered compared to OTL.
5) EU-US split. The general trope here is to have a Sino-Soviet style split occur in the West during or after the Cold War. There may be some PoDs for it- US doing some very disgracing moves in foreign (using nukes in Vietnam or actively backing far-right regimes in Southern Europe) or internal policy (electiong some very far-right far-left, or isolationist president), UK never joining the EU or EU focusing on turning itself into a full-blown federation. Overall, the stablishment of a Euro military pact as an alternative to NATO is likely in such case and that pact may establish good relations or even outright incorporate Russia/moderate or reformed USSR. So, the Moscow here would be able to realize the strategy of "Europe from Lisbon to Vladivostok" and becoming a counterbalance to the American influence.
P.S. Just a standalone bonus PoD: Remove the West German recognition of the Oder-Neisse line (No Brandt chancellorship basically) and it would cause a lot of problems for NATO expansion into Eastern Europe with chief continental European ally of US (FRG) having a major dispute with chief NATO aspirant- Poland.