Try tossing in some Starships. Flagships are a straight %-damage boost to your other ships, Heavy Bombers and Plasma Siege hit pretty hard. If you got it done to 60% with just fleet ships, Starships (and I'm talking just Mark I Starships that you start the game with) might be enough. Interesting, the Teuthida might count as a Sniper and Scout Starships give Sniper immunity to ships around them. So if the Teuthida was doing most of the killing itself, pack in Scout Starships in your attack to reduce your casualties (the immunity circle is pretty small, so bring multiple to increase their coverage). And yeah, I'd say bring the Champion. The more the merrier!