Instead of lockboxes to obtain new ships, have the players purchase 2000 C-points to unlock the ability to obtain the ship, then have the ship cost something to purchase it. For example, the Galor class could cost the player one million dilithium to obtain(which would make sense since the Cardassians are rebuilding their infrastructure. The D'kora could cost like 20 million latinum which would make sense as the Ferengi crave it. The Jem'Hadar attack ship could be obtained by completing a 10-mission Doff chain(with the catch that all parts of it are successful - any failed missions must be repeated until successful)[
I've thought it over and think this would be a really good idea for the C-Store. There are people who reallly do not like lockboxes. What I posted above would allow other players to obtain non-faction ships without going through the hassle of a lockbox. I would amend the above in that I would lower the C-point cost to 1000 from 2000.
Another way that this could be done is if purchasing an unlock from the C-store would allow the players to purchase the desired ship from a special vendor. This vendor would only appear after the player purchases the unlock. The vendor could require a mix of commodities in order to purchase the vessel such as dilithium, ECs, rare crafting mats, and certain items that could be replicated such as self-sealing stem bolts. A Dominion vendor to sell the Jem'Hadar attack ship is questionable as the Dominion wouldn't sell technology to their enemies. However, maybe a race other than the Ferengi could sell it. If you wanted to have a Dominion representative sell the ship as well, it could be argued that the Dominion has created a better version of the same ship and could recoup those "reparations" they had to pay because of their war with the Alpha Quadrant. A D'Kora could also be purchased from the GPL store instead of going through a vendor.
These are some ideas that I have but I think this is a win-win for everyone as there are people who like the lockboxes and those who can still obtain the desired ship, but just in a different way. Cryptic wins as they will get more money. Besides, if the ship is good enough, then players won't mind doing a grind for it.