As BGG noted, one For the Fleet's biggest similarities to BSG is the premise. So we need a new theme. I don't want to move away from scifi, though. Folks were really creative with those ships!
A retheming should also explain the victory condition, which in For the Fleet is a little odd. You'd think the victory condition should simply be surviving for X rounds. But in For the Fleet, you're trying to earn X victory points before Y rounds. A subtle difference, but one that should be at least make sense with the new theme.
So here's a quick stab at a new pitch and new theme.
Pitch: It's Zap Brannigan's Catan with a dash of Han Solo. The kind of game where carelessly throw red-shirted henchmen into the harm's way. The kind of game where you might shout "Stop dying, you cowards!"
Theme: You're captains of a ragtag rebel fleet – a mish-mash of antique military ships, smuggling freighters and retrofitted pleasure yachts. You're on a supply run for the rebellion, pursued by imperial forces. The rebel fleet can warp ten times before being caught, so make the most of it!
Altered Terms: The Jump Deck is renamed the Warp Deck, to distinguish from BSG a bit. Instead of harvesting asteroid belts and uninhabited planets, you raiding the empire's ships, colonies and outposts.
Art: I see the art being a bit cartoony, like Futurama meets Team Fortress 2. Exaggerated features, puffed up chests, cunning winks, and evil goatees.