changing non resident address to a Portuguese one.

No, it's not. I changed my address  from non-resident to resident with the proof of address (rental contract) and my wife got her NIF with Portuguese address without representation 6 months before getting her residency card using the same rental contract.

I changed mine using the Atestado de Residencia (Residence certificate)  I got from the local parish (Junta de Freguesia). They need deeds or rental proof to give you the certificate. Then you have an official document proving your address, the financas at both Alcobaça and Porto de Mos accepted this.

Don't be surprised if you can't, though.  I've gotten a variety of stories on this.  Anecdotally, people have succeeded, with some help.  I tried the AT web site, where you can make a request, and it was denied - I'd need título de residência (com validade à data do pedido no SEF) or pedido de manifestação de interesse.  I understand the latter to be a step that you'd take when starting work in Portugal prior to SEF residence, i.e. only applies to someone working in Portugal.  The realtor gave it a shot at the local Finanças office, and was told I might be able to get it if I had a SEF appointment.  The success stories I know of all transpired at local offices, not the AT web site.  There may have been changes in policy, and some local officers are going off the old policy, or they just don't know or care about whatever rule is involved here (Instrução de Serviço nº 90052/2022, de 18/03 - apparently starting March 18, 2022?)

@donn25 hello , can you tell me where I can find the law/directive (Instrução de Serviço nº 90052/2022, de 18/03 - apparently starting March 18, 2022.

I am asking because registering with tax authorities(obtaining NIF) is one of the requirements in order to apply for a residence card, yet at the same time , we cannot change to Portuguese address without residence card. Is SEF aware of this?  is there someway way we can show the SEF officer/agent that it is a catch 22 situation.

Does SEF (for the interview for residence card after issuing D7 visa) accept NIF and other proofs with foreign address on it?

Nope!  I looked for it myself with no success.

Mainly this isn't a problem.  For the purposes of official residence process, sure, everyone has a foreign address for a while, with a national representative.

It's incidental problems I'm concerned about.  One is that the household import, with baggage certificate, may require a Portuguese NIF address, or you blow the VAT exemption.  (This seems excessively ridiculous to me, but that seems to be the story.)  Another is a detail concerning property taxation and primary residence, and I guess it will just be interesting to see what happens.   Those are the only things I can see where it might matter.

Coincidentally I just stumbled across another version of the story, from a Finanças FAQ,

https://info.portaldasfinancas.gov.pt/pt/apoio_contribuinte/questoes_frequentes/Pages/faqs-00303.aspx

Item 11-4649 Quais os documentos que devem ser apresentados pelo cidadão estrangeiro, nacional de país terceiro, para comprovar a alteração de morada, quando esta implique a alteração de não residente para residente?

Here again they appear (c) to allow a SEF appointment, if you don't already have (a) a residence permit.  (There's also a mystery clause (b) that refers to various articles that I haven't tried to look up.)