Thanks for the kind answers, lumiere and Gunner98! I specially appreciate Gunner98's breakdown of ship classes in difficulty levels, because I really have no notion of naval unit composition. My thing has always been air & land combat, naval is my blindspot.
The idea for this scenario came about when researching the A-7P Corsair of the Portuguese Air Force. Originally, the PAF wanted the F-5E to replace the F-86 as an air defense fighter, but the country was cash-strapped after a 48-year dictatorship and a 14-year, 3-front African colonial war. The only thing we could rely on was the compensation for the American use of the Terceira Air Base in the Azores, which was valued at 72 million USD. A full squadron would cost 120 million USD, an unbearable expense at the time. Since we were a rear guard NATO country, one of our tasks would be to patrol Atlantic shipping lanes to protect US reinforcement. So the US offered refurbished A-7As with upgraded electronics for 64 million USD, which was cheap enough to allow us to buy another C-130, another PAF ambition at the time. And for air defense, the A-7P would do in a pinch.
So that gave me the idea of a Soviet SAG running wild in the Atlantic, raiding NATO supply lines, and the Portuguese Air Force, outgunned and outclassed, flying in Vietnam-era relics to sink those leviathans of sea!
So, in order to give the PAF a fighting chance, it couldn't be the Kuznetsov (the Sukhois would mop the floor with the Corsairs) nor any modern Soviet air-defense ships (ditto for the S-300F).
The Portuguese Navy at the time was more than irrelevant, as it was still an all-gun navy. (The first AShM-equipped vessels in the Portuguese Navy would be the Vasco da Gama Class, acquired in the early 90's!) So this would be mainly an air power scenario, perhaps with a submarine thrown in for good measure.
NATO support would be limited to air-refueling planes. Besides the A-7P, the other PAF aircraft in this scenario would be the Orion, which besides providing long-range radar, is still today the only aircraft in PAF inventory to carry an AShM.
As for the plot, well, you'll have to wait for another day, as this post is getting long enough as it is...
TL;DR: Thank you very much for the info!