But yes F-104C was more than adequate for the air superiority against MiG-21/19/17 that the VPAF had, both in turning and in climb rates. The USAF's only problem was the thing between the instrument panel and ejection seat was getting in the way. A gunfighter able to get the drop on VPAF fighters through a rear upper quad dive with radar controlled intercept is more important given the tight ROEs of Vietnam and its occasional cloudiness.
One that can turn, which F-104 can only sorta do, really helps mediocre pilots too since they'd more often find themselves in disadvantageous situations requiring being able to pull a nose onto the target and press the trigger rather than dominating the fight from better initial positions.
Without actually good missiles (AIM-7M or better, or AIM-120) though the F-104S would be only of marginal capability in combat really. All the various 1960's radar guided systems were still extremely primitive and prone to failure in ways that 1980's ones just weren't, which mostly explains the radar guided kill discrepancies of Vietnam versus Desert Storm and Kosovo. This is especially true for a single seat fighter. I'd imagine the bulk of air combat victories with the Phantoms were due to the fact that the workload of operating a clunky pre-digital AWG and actually flying the thing were split between two people. The efficacy would be reduced if both of these jobs are done by one guy on a maneuvering fighter.
Starfighters would need to be flown like Phantom in that they'd thrust for vertical rather than horizontal maneuvering during the fight, but fought like Crusader in that they'd be lining up cannon shots by stalling out the opponent or diving from high angles. Starfighter has a low frontal profile and is hard to spot in general in air combat, and with AIM-9C would have near identical performance to the R-13 in frontal aspect target engagement, and overall both MiG-21F-13 and F-104C were pretty similar, so it would come down to who gets the drop on whom more or less.
Since Feather Duster only focused on the MiG-15/17 subsonic threat, it's hard to say how you'd counter MiG-21s specifically, but I suspect it would be similar to Bolo overall (MiGs roll up for a strike package assault and the main/high altitude escort force head-ons the -17 frontal wave with AIM-9Cs while the MiG-21s are dropped on by a rear guard force) just with more airborne tankers and EFTs overall.
In practice the Phantom was just a IP Starfighter in terms of general use and operational methods, and could better employ the Sparrow in close combat than any preceding fighter in Air Force inventory, at longer ranges, for longer on-station periods. Starfighter just lacked the legs of Phantom and the F-104S lacked the WSO, so it wouldn't matter much in a dogfight. So you'd see more AIM-9Cs being purchased for frontal engagements, and the USA might shift to using AIM-9Cs for all aspect use rather than canning them when the Crusaders were retired, until the Lima drops a decade later and negates the need for R-13-style radar guided weapons for frontal aspect use.
Loss rates would still be high simply because the USAF was poorly trained and poorly organized for limited war/conventional air superiority sweeps, and the Soviet-American technological gap was much closer in the '60's than it was in the '90's or today, so the men still mattered a lot. The Vietnamese were well trained, well led, and well advised, and had a lot of grit. There's very little to be done to permanently put out of action a motivated, well trained air combat force when your technological and materiel advantages are so slim, at least from the air.
Vietnam was just the closest America ever got to fighting on the Eastern Front or during the London Blitz, tbh. Neither side could knock the other out with their allocated forces so it became a battle of attrition, which America wasn't willing to sustain, and the Soviets were willing to supply the Vietnamese with aviation for days. Short of physically occupying or destroying airfields with armored divisions, which America explicitly rejected, and which was the Soviet solution to Nazi airpower, or resorting to nuclear combat, which was the Combined Bomber Offensive solution, there's not much to be done as far as the USAF was concerned.
It just didn't have that experience that the USN did in air combat to give it the necessary knowledge framework to break free from its past. Vietnam was the learning experience that the US Navy got in 1942 staring down the gunsights at what may have been the most elite and well trained tactical air force the world had ever seen. Well, until it got chewed up in the Solomons campaign and never really recovered from its death by a thousand cuts.
You'd ultimately need to fundamentally alter the US Army Air Forces' ETO combat experience, or somehow ensure that it engages in main combat actions against a much stronger Japanese-style opponent, or something like that, as that is ultimately the root of the USAF's failings in Vietnam and planes can't change that.
This is ultimately just the outcome of the differences between land-based, continental/strategic aviation and the more tactically focused, nautical aviation that focuses on gaining ground for the strategic aviation to base itself off. Making the USN bigger, having shore-based tactical fighter squadrons for the Pacific, and being entirely in charge of the air ops of the Vietnam War might help unironically in cutting loss rates, but that would make the USAF really mad and all the branches were trying to legislate their opposites out of existence after Operation Crossroads by arguing that nuclear weapons were the only real need in combat.
The Korean War just put a three year pause in that debate which was ongoing well into the combat phases of Vietnam and that parochialism is a big reason why the US could never form a coherent strategy.
F-104C/-S and F-4C/-E would likely produce near identical loss rates in action, but the methods of killing enemy aircraft for the F-104s would be far greater proportion of AIM-9s and 20mm and much of fewer AIM-7s due to restrictions of ROE and lack of a WSO. Without the backseater and gun, the F-104S would also be worse in practice than -C I'd think, unless you gave it a radar fit comparable in automation control technology to the the APG-70, MFDs similar to the -C or Alfa Hornets, and AIM-7Ms with the autopilot and low altitude fuses.
It's probably important to keep in mind that the Soviets in the '60's and '50's were still extremely responsive and dynamic in their industrial throughput, and were more than able to keep pace with US developments until the 1970's. Analogizing the MiG-21F-13 quite literally as "a F-104S with a toy gunpod" wouldn't be incorrect in general performance characteristics, and the VPAF more or less was built as a mincing machine for denying American airpower from the start.
Due to the larger macroeconomic factors at work in the Soviet-American economic competition during the '50's and '60's, the fate of most US pilots in Vietnam was decided by the fact that automation and general technical characteristics were still too weak of influences versus man-pilot characteristics. There's very little to change this without altering these fundamental factors, like giving 1980's-era electronics to the USA (or Soviets) instead, or something equally wacky. Even then, the strict ROE and limited war conditions would still mean someone's F-15C is getting creamed by a MiG-19 from negligence.
Naturally none of this would have altered the vast majority of US losses in the war either, most of which were due to AAA fire, with fewer than 4% of US fixed-wing losses due to PVAF fighter action, too. The USA only records around 95 aircraft being lost to enemy air action, while the Vietnamese claim something like 200, so it's between 4-8% of losses at the most extreme ends.
American air losses are wildly overstated (due to emphasized marketing from "POW" lobbying concerns from the 1980's mostly) and something like JDAM (perhaps a LORAN INS guided weapon?) able to be used from 10,000-15,000 feet and above the clouds would have reduced losses immensely and immeasurably more than literally anything else.