IMHO, the show's first misstep was to get both factions to become cozy picnic friendly after the grueling antagonistic sparring in two episodes. The show sold a good premise but never really took it anywhere. Except backwards.
Technobabble felt a lot more lax.
VOY, for all its potential, often tried to feel like "more TNG", trying to recapture season 2-4's feel but not quite succeeding. Were people clamoring for more comfy Trek feel at the time as opposed to more gritty DS9?
One could argue "Trek Burnout(tm)" was starting to creep in as season one, while passable, wasn't as engaging as it could be.
Season 3's "Worst Case Scenario", had VOY been made the same way today, would be perceived, misperceived, and/or heralded as a "Froofy Unicorn to the critics in the audience" as it starts out with a great premise but becomes a magical mockery with the holodeck, amazing what Seska could do in such a short time to all of those ship systems, years before leaving, and nobody noticed. (All in all it's a good premise, ultimately let down by a couple of moments and maybe not being a two-parter to let the good stuff breathe and develop instead of rushing to the ending.)
The other big mistake would be, of course, how the ship never got worn down or ever looked battered for more than one episode - "Year of Hell" encapsulates what many would rightfully expect VOY to explore since the premise pretty much states they're out there, truly alone. Then the selective reset button gets hit and everything's all pristine and perfect again. The show had a great premise but didn't often use it as more than a gimmick.
At the same time, other sci-fi shows of the time were exploring different ground and ideas, and given VOY already had Trek Legacy and Baggage being lugged around, people would have passed it off at the time saying "it's just trying to do the same thing as those shows, with no originality or innovation or anything different", especially as DS9 was doing the war arc and rather successfully... There was just no way for it to win, at the time, since TNG and DS9 did it all already and there was no new spin or facet... Except there was, as told in the premiere, but they didn't run with it. And the TLaB seems to be an integral reason to that.
But it kept enough viewers to get through seven years so it wasn't a flop.
And if Space 1999 could go through Eagle ships like candy, so can Voyager's torpedoes.
VOY did have some good, robust, and classic episodes. Some of which were the sort only VOY with its premise could do, but others would have worked just as well in TNG but weren't thought of at the time. "Worst Case Scenario" (even with Seska's holodeck magic and all, it's still largely a great episode) and "Blink of an Eye" are respective examples of VOY only/TNG extension.
And, indeed, the addition of the Borg, until they got buried into the ground, was ingenious. Better yet, Seven - despite apparent offscreen animosity - lead to what I thought was a great double-act between Janeway and Seven for discussing humanity the way that hadn't been pursued with Tuvok (though I appreciated how Vulcan sociology was explored via him.) The fact they got the excellence of Jeri Ryan -- before anyone says "They just hired her for T&A", check out her work in "Boston Public", she's a great actor. "T&A" doesn't maintain ratings unless it's "Baywatch" or "Jerry Springer". And even then.
The show did have its missteps, but so much would be overlooked because of Trek's lengthy lifespan and the Trek Burnout that came with it.