If R* did make a Stories series based on San Andreas, it would have to be in one city and (to a lesser extent) the land since the whole map wouldn't fit in PSP. That's why I think it should have three different settings in each city:
GTA Las Venturas Stories could be set in sometime in the 1970s (my pick for the year would be 1978). Not sure who would be the protagonist, but they should at least show how Tenpenny became corrupt and such, you know, have him play a similar role as Sal in San Andreas, only with a much bigger role.
GTA San Fierro Stories could be set in the late 1980s, either 1988 or 1989. We could play as one of the member of the Mountain Cloud boys, see how they got in it with the Local Syndicate. We could also know more about Wu Zi Mu and/or the three members of the Local Syndicate.
GTA Los Santos Stories could be set a year before the events of San Andreas. I made a topic about it here: If there was a "Stories" game for San Andreas... - GTA San Andreas - GTAForums
Of course, other characters that could be the protagonist of Los Santos Stories could also be Big Bear or Ryder's homie LB.
Also, the introduction doesn't really count as a "prequel" since we only seen the things that happened a day prior to the game's story. It was just only what kick-started the storyline. We didn't get to see a deeper look on the Ballas and who their leader was. We never got to see how the Seville Blvd and Temple Blvd families started beefing with each other. Also, Brian was a child when he was killed. So even if the storyline took place before 1987, he would still be too young to play as, let alone even capable of appearing in GTA at all.