Privateer is a good example. Several story lines as well as open gameplay and random encounters also available. You could follow the missions, or go off and do your own thing.
Some immersion is nice. In the original Starfleet Command from Activision, you acquired officers which grew in abilities, who you could transfer for better officers, and who could be lost in the line of duty if things went bad.
The story line of the Interstate '76 line from Activision were fun. So were the Wing Commander series, although sometimes they may have inserted too much of it.
In Shadow Company: Left For Dead, you grew a roster of merc, which could grow, develop, or be lost. You develop an in-game attachment or empathy toward these characters, in games like this.