Keep the three characters but expand the story over a timeline.
Start out in a snowing Carcer City in the 1970s, where you are a member of a small-time crime family who are being taken over the new Bureaucratic/Corporate organized crime outfit (with offices and all). Leads to a war where you manage to escape as your crime family is taken out.
Move to Vice City, it's the 80s and you're can commit petty crimes where you can snatch purses or stand-over people. You save another criminal who is a