Having won election on a platform of change, Gov. George E. Pataki used his first address to the Legislature today to make clear that the first thing he intends to change is the governor's relationship with the Legislature.

It is probably the most important thing his fledgling administration can do. Without a strong working partnership with both houses, one of which is controlled by Democrats, Mr. Pataki, a Republican, has little hope of accomplishing his larger goals of cutting taxes, shrinking government, toughening criminal penalties and reducing welfare spending.

Former Gov. Mario M. Cuomo's dealings with the divided Legislature were often bitter, and one result was deadlock on many of his major proposals. Mr. Cuomo, a Democrat, even blamed the Republican-controlled Senate for keeping him out of the 1992 Presidential campaign by delaying passage of a budget.

Mr. Cuomo had two problems with the Legislature: personally, he disliked having to pat backs and twist arms to push his proposals through, and ideologically, he often found himself at odds with the Republican agenda. Mr. Pataki pushed the first problem aside today by telling legislators that "friends always stay friends -- the door to this Govemoes office is always open to you."

On the second, he put his former colleagues oiti,;hotice that his conciliatory tone stretched only so far. "But I also want to point out that under our democratic system. our first duty must be to keep faith with the people of this state," he said.

Time and again, he reminded them that he was one of their own: he served eight years in the Assembly and two years in the Senate before becoming the first man in 140 years to be elected governor directly from the Legislature.,Time and again, he sprinkled affable references to individual lawmakers into his speech, like a successful graduate telling his old fraternity brothers that he hasn't forgotten them. He ended the 45-minute address with a passage titled "A Lawmaker's Perspective."

"Ten years ago, during my first day as a member of the Assembly, as I listened to the Governor deliver his State of the State message, I sat in the seat where freshman Assemblyman Jay Dinga is sitting now," Mr. Pataki said, referring to a new member from Endicott. "I felt privileged then, and I feel privileged now, to be part of this great institution.'

But Mr. Pataki sent a gently menacing message to those who might block his initiatives. Oppose me, he suggested, and you will face the wrath of an angry electorate.

"In recent elections, the people have shown themselves not only willing to make changes, but to go right on making changes until those of us elected to office get it right," he said. He has shown the capacity to deal harshly with those who contest him -- as Senator Ralph J. Marino, who opposed Mr. Patakils candidacy, learned last Thanksgiving when Pataki supporters ousted him as Senate majority leader. And he told them, albeit with a smile, that if they did not pass a budget on time, he would block their paychecks.

Whether Mr. Pataki's efforts to improve relations with the Legislature will pay off in legislative successes remains to be seen. Today, even as they praised his openness, Assembly Democrats, particularly those from the New York City area, said that they still disliked the substance of Mr. Pataki's ideas.

"In a 45-minute speech, he never once said the words New York City, never once said the word AIDS, never once mentioned the subways," said Assemblywoman Catherine T. Nolan, a Democrat from Queens. "He was nice and pleasant. But we worked with him for eight years. I wouldwt have expected anything else."

Some critics also found Mr. Pataki's speech heavy in political symbolism but thin on policy. Thomas Sobol, the state Education Commissioner, said that Mr. Pataki's proposal to eliminate the Board of Regents and to slash spending on the state education bureaucracy would save little money and do nothing to improve education. "It makes good political theater, but its not the realities," Mr. Sobol said. "The campaign is over. It's time to govern."

But there were some Democrats who found Mr. Pataki's words heartening. "For too many years there has been an enormous amount of insitutional friction between the 'governor and the Legislature," said Assemblyman Steven Sanders, a Manhattan Democrat. "To the extent that friction can be diminished is a good thing."

A large measure of reducing the friction will be how well Mr. Pataki works with the Assembly's most powerful member, Speaker Sheldon Silver, a Democrat. The new Governor praised Mr.Silver today as "a good leader, a good friend.' But during the campaign, he said that he was prepared to lobby individual members directly if he believed legisla leaders were stymieing his proposals.

Mr. Pataki hinted that he would seek the support of moderate and conservative Democrats by singling out one of them, Assemblyman Richard J. Keane, a Democrat from Buffalo, saying: "Nice to see Assemblyman Keane clapping back there. We need your vote, Dick."

Mr. Keane is one of about 20 Democrats front-..upstate districts, most of which overwhelmingly supported Mr. Pataki. He will need almost all of their votes to pass his initiatives in the Assembly.

Assemblyman Jacob E. Gunther 3d, a Democrat from Monticello, is another one of those Democrats. Calling fiimself "the lone Democrat in the surrounding 13 counties," Mr. Gunther said there was little in Mr. Pataki's speech that he disagreed 'with. And he suggested many of his Democratic colleagues would feel the same.

"I think the Assembly as a whole understands what the last election was about," he said.