I played Grand Theft Auto: Vice City for the first time a year or two ago, and what astounded me was that the game would occasionally switch things up on the map depending on where you were in the story. For example, when you completed the Cuban/Jamaican subplot, the Jamaicans would attack you whenever you wander into their territory. III did that as well; the farther along you were in the game, the more people were pissed at you and would attack you when you got on their turf (though personally I found that more irritating since it accounted for the whole island and not a small section like VC).
