An idea is that everyone start neutral to eachother and you have to specifically declare war on someone before your ships attack another factions ships.
Diplomacy is hopeless as the one you intend to make an alliance with somehow always gets in the way, with a ship shot down and diplomacy rate lowers thus making any progress insanely hard.
Diplomacy with factions of the same race should start with a small bonus from the start.
Until you actually meet with another faction you shouldn't even know who they are, make them hidden, sort of like when the pirate is dead and unavailable.
Add more options, like suggest going to war together. Have a look at Civilizations and you'll get an excellent idea of how diplomacy could work. Defensive pacts, and so on.
