How about...
We add a new Trueskill rating but instead of skill it tries to rate CPU of players and adjusts after every match!
For each game we figure out the slowest CPU (if we can do that?) and then we tell Trueskill that that player played and lost against all other players of the match in several 1v1s. Over time Trueskill should come up with a ranking of all player's CPUs ??? xD