So, what games are these and how do they do it? Tell me more!
Well, I'm thinking mostly of HeroWars/Quest and Burning Wheel. If you know these games already, then skip to the last paragraph to see why I think the sorts of techniques they use might help deal with the "making things different" issue!
A PC for HeroWars/Quest is, in mechanical terms, a list of free-form descriptors with numerical ratings. The basic resolution system uses opposed rolls to determine success levels for winner and loser. Relationships, followers, reputations and so on are just more attributes that can be used to resolve contests. To give an example: The goal, in play, is to learn who the head of the evil cult is. My PC is the leader of the beggars in the city and wants to send them out to gather rumours. Mechanically, this could be resolved as a contest between my PC's Beggar Guildmaster attribute and the cultist's Manipulates From The Sidelines attribute.
Two mechanical complexities have further implications. First, attributes can be used to augment other attributes that are then used to actually resolve the contest (a bit like secondary skill checks in a skill challenge). So in a fight to defend my barony against invaders, I could use my Born To Rule This Land attribute as an augment for my Tactical Leader or Cuts Down Orcs Like Chaff attribute. Even equipment in HeroQuest is an attribute - so my ruler can have the Impregnable Castle attribute, and use that to resist the orc horde's Cut A Bloody Swathe Across The Land attribute. Second, there are also pretty well-developed community rules that allow players to draw upon their PC's communities to get additional augments, at the risk of depleting the resources and loyalties of those communities.
Naturally enough, playing out these sorts of contests is going to be fairly abstract in parts. When I use my Beggar Guildmaster attribute, I'm going to talk in general terms about what I'm doing to bring it into play - it's a key part of HeroWars/Quest that the GM and the player each explain what is happening in the gameworld as part of the process of mechanically framing the contest (again, a bit like a skill challenge) - but we're not going to resolve every little aspect of every single beggar's adventures as they collect rumours and learn the truth about the cult. This is a cost of keeping it a single-PC focused RPG - once you have detailed resolution for this sort of thing, or for the invasion of a barony, as far as I can see you're playing a wargame or something similar.
Burning Wheel's mechanics are less generic and suitable for abstraction than HeroWars/Quest, but there are rules for Circles (= contacts) and Reputations/Affiliations (various sorts of augments to Circles) that can then be used as attributes to resolve contests - mostly social/political contests - in the same way that skills can be used.
If your game unfolds in such a way that low-level PCs mostly have skills and attributes that are about what they, individually, can do, but then gradually evolves over time so that more and more of the PCs' attributes are the sorts of relationship/follower/reputation abilities that I've been talking about, then the nature of play would change fairly dramatically - instead of the PCs guarding caravans and fighting orcs as mercenaries, they would be planning and leading caravans and commanding the guards that fight off the orcs - even though the mechanical systems in play had not changed, and the game retained a focus on individual PC personalities.