When I didn't speak any Russian, yes, Portuguese, even the one spoken in Brazil, sounded like what I imagined Russian to be. Now, the language spoken in Brazil doesn't sound anything like Russian to me. Totally different intonation, rhythm and many sounds that they don't share. As for the one spoken in Portugal, sure, there are one or two similar sounds in Russian, but I wouldn't go so far as to say European Portuguese sounds like Russian or other Slavic languages.
I don't really think Portuguese sounds like French either. French doesn't sound like any of the other Romance languages to me, except sometimes, maybe, Catalan.