Washington's relations with Moscow are troubled by sharp disagreements on specific issues - in particular the U.S. proposal to place elements of a missile defense system in former Soviet satellite countries, and by a clear rise in the Kremlin's suspicion of American intentions worldwide.
Russian officials bristle at U.S. criticism of a perceived Kremlin rollback of democracy and complain that Washington is interfering in the country's internal affairs by funding pro-democracy groups. Russia also accuses the U.S. of trying to dominate international affairs.
In an address on the anniversary of the defeat of Nazi Germany, Putin last week denounced "disrespect for human life, claims to global exclusiveness and dictate, just as it was in the time of the Third Reich."
Along with missile defense and democracy, issues likely to come up in Rice's meetings include Russia's resistance to a U.S.-backed draft U.N. resolution supporting independence for Kosovo, Putin's call for a moratorium on observing the Conventional Forces in Europe treaty, and Russia's increasing control of oil and natural gas supplies that are critical to Western European countries.
Despite the tensions and the emotionally fraught rhetoric, Washington and Moscow have tried to emphasize areas of common concern and cooperation including the international fight against terrorism and increasing cooperation on securing nuclear facilities.
"On many things, we have done very well, but the fact is that on some others it's been a difficult period," Rice said of Russian-U.S. relations last week.
The assessment was echoed by Deputy Foreign Minister Sergei Kislyak.
"Russia and the United States have many issues that we either cooperate on, or that we need to review our positions on," the news agency RIA-Novosti quoted him as saying in an interview. "We are expecting a serious discussion on serious problems, both from the perspective of our own security and of European security."
That statement indicated the U.S. missile-defense plans will be at the top of the agenda. The United States wants to deploy elements of the system in Poland and the Czech Republic, saying the system is aimed at responding to possible missile attacks by countries such as Iran and North Korea.
Russia dismisses the prospect of such attacks and says the new system would undermine the global balance of security. The Russian military's chief of staff, Gen. Yuri Baluyevsky, in recent weeks has repeatedly said Russia could consider system elements in Eastern Europe as potential targets.
Foreign Ministry spokesman Mikhail Kamynin said in remarks published Monday that any European missile defense plans should be a matter for discussion by all interested countries.
"We proceed from the assumption that questions of missile defense on the European continent should be considered in a collective format and answer the security interests of all European states. So we call on the U.S. to take such an approach," RIA-Novosti quoted Kamynin as saying in an interview. He said Russia is also willing to discuss the issue with NATO and one-on-one with the U.S.
Nikolai Borduyzha, the secretary of a security alliance linking Russia with several ex-Soviet republics, said the "very presence of missile systems, whatever their purpose, is alarming," Interfax reported.
"For the first time in history, elements of U.S. strategic forces and NATO may appear in the immediate vicinity of the borders of Russia and Belarus," he was quoted as saying.
Washington in turn looks at Putin's consolidation of power and sees a dangerous retrenchment on basic democratic principles. The U.S. is also unnerved by Russia's growing energy wealth, its apparent use of energy as an instrument of political pressure, and centralization of the once entrepreneurial energy sector.
On Saturday, the leaders of Russia, Turkmenistan and Kazakhstan reached a landmark pipeline deal that will strengthen Moscow's control over Central Asia's energy export routes. The agreement sets back U.S. and European efforts to secure alternatives to Middle East oil and gas that would be independent from Russian influence.