You know, I have been thinking again... which is never a good sign...
What if... instead of (or at least in addition to) story based in game relationships or romances as some special event... you could merely "tag" any NPC for a relationship. The NPC you tag could be either someone from the story, or even just random person walking down the street.
Once tagged, the NPC will have a dialogue tree, allowing you to ask them out, "roll your seduction" if you will. If you are successful, then at that point you can choose to continue the relationship, and how serious it becomes... for instance you might choose to keep it platonic, then they are just your buddy, wherein you get their number, and can call them up to run around with you, ... If you choose a casual romance, maybe in addition to the number and hanging out with them, you can get a bit of the old in-out, in-out... If you choose to have a deeper relationship, maybe they move in to your safehouse, so in addition to calling them, and having them hang out with you, they are there hanging out at your house.
If they get killed while you are hanging out with them they are dead, so be careful where you take them, and how fast you drive with them with you.
You should be able to "Tag" multiple NPC's for relationships, but if you have too many, especially if they are hanging out in the house with you, then they have dialogue options where they get "jealous"and take off.
The difficulty for random NPC seduction should be varying, but it should be possible for just about anyone.
Of course logistically, from at least a resources viewpoint, the Dialogue trees for the NPC's would be pretty limited and repetitive, but no more so than the random comments and conversations of pedestrians as you pass them on the street in most sandbox games anyway... Hell, make most of the relationship dialogue trees for NPC's text based, then they eat up almost no resources at all, and this way you could even give them a number of distinct personality traits...
I don't think this would be all that hard to implement... if you look at a game like Saints Row where you have "homies" you can call to run around with you, or in SR2 where your cribs were always full of assholes and hookers, its not really much of a step from there. In San Andreas even you could randomly grab gang members and run around with a crew. In GTA 4 you could have girlfriends, but they were vapid and shallow, and you were limited in your choice...
With an option like this, when you see that sexy chick, or dude, walking along the beach, you could tag her/him... and the possibility to make them a friend or lover would become available to them.
Some storyline NPC's it should be possible as well, obviously some would have more inclination towards this angle as well.... For example Kinzie or Shaundi from SR, or Pierce if you play a female protagonist... where there is already flirtation... Then if they do die in the story, it is made all the more tragic...
Antagonistic NPC's would either not be possible to romance or befriend, or be near impossible... due to the whole they want to kill you thing... Although perhaps it should be an available option for some of them after they have completed their sections of the story inclusion, and survived of course. It would be cool to make friends or lovers out of former enemies and rivals...
Thoughts?