The Cybermen aren’t alone in the universe but it is rare to see them interact with any other species. We had to wait until 2006 to finally see them encounter the Daleks in ‘Doomsday’.
Imagining connections between other alien races is a good source of new adventures. Not only that, the more you have species meeting the more the universe feels like a living place. The more connections you establish the great the intermeshing of events.
Daleks
In ‘Doomsday’ the Cybus Cybermen propose an alliance, stating that the Daleks technology is compatible. The Daleks reject this offer but this need not be the case in every situation.
Certainly the Daleks will pretend to ally themselves with others when it suits their purpose. Eventually they’d betray their allies but then the Cybermen would as well. In ‘The Five Doctors’ the Cybermen made it clear that promises were meaningless to aliens.
What would the outcome of an alliance between the two races be? The Cybermen could certainly benefit from the Daleks weaponry and possibly their ability to hover and fly. This would make them much more efficient at combat.
In return the Cybermen could help the Daleks optimise their design. Their original construction was developed by Davros and so they may lack the ability to improve upon it. The Cybermen update themselves on a regular basis so surely would have ideas about how to improve them.
It has been stated that Daleks have been motivated by pure hate but they do demonstrate other emotions. They are prone to fear, especially if their vision is impaired, and fits of depression can lead them to killing themselves.
A Dalek with a emotion inhibitor could prove to be a great boon for them. They could still feel hate but any other emotion could be eliminated. How much more could they achieve if they eliminated their own pride?
One piece of technology that they already seem to share is the conversion process. In ‘The Dalek Invasion of Earth’ the Daleks first make use of Robo-men. They wear helmets and brain washed into being loyal zombie servants of the Daleks.
This is so similar to how Cybermen covert humans that this can’t be a coincidence. Did the Daleks steal this technology and if so does this mean that Mondas passed Skaro in its wandering through the stars? Alternatively is this an indication that there was already an alliance between the races?
Inevitably one side would betray the other, the only question is who would be first. If they exchanged technology the obvious fail safe would be to include something that would allow the subject to have their loyalty changed.
One can imagine brightly coloured Cybermen with their recently installed death rays turning on their brethren and silver Daleks turn on their own race when new programming shuts down their emotions and orders them to kill for the Cybermen.
It does seems as if the Cybermen and Daleks would always be in conflict. Both have a stated goal to conquer the universe. Whether the Cybermen convert the Daleks or are wiped out remains to be seen but innocent people could be caught in the cross fire or used as pawns.
An interesting possibility is if the Cybermen began providing technology to worlds that have been conquered by the Daleks. The Cybermen would then be able to set back the Daleks plans and create a population who have become dependent on their cybernetics. They’d then be able to come in and finish the conversion protest.
Player characters could arrive at any stage of this plan. If they are then when the rebels are overthrowing the Daleks the time travellers could recognise the technology being used and suspect what will happen next. When the Cybermen arrive could the player characters convince people that they aren’t saviours?
Ice Warriors
The Ice Warriors would have been neighbours to Mondas, as well a those of Earth but what if the link between the two is stronger. We know that Cybermen were originally nearly identical to humans. Two species developing on twin worlds and developing along different paths.
If Mondas truly was a twin to Earth what other species might also have developed. We know that the Ice Warriors are a reptilian humanoid race who use cybernetics and have tombs in which they place themselves in stasis. Could they be Mondas’s version of the Silurians?
The Silurians went into hibernation due to events that never occurred on Mondas. On that world the two species could have lived side by side, both coming to use cybernetics. When the planet began to leave the solar system could the reptilian race have abandoned their home world to make a new life on Mars?
They even share similar modus operandi. Both first made appearances in snowy locations (the Cybermen at the South Pole and the Ice Warriors during an Ice Age) and then attempting to see control of a moon base. The similarities are uncanny.
What would such a connection mean? Would the two species even be aware of it?
If the Cybermen knew could they use this information to forge an alliance with the Ice Warriors? If the Cybermen told the Ice Warriors that Mondas, their place of origin, was destroyed by the humans could this motivate them to jointly seek revenge?
The difference between the two races is that the Ice Warriors have a lot of personality, following a warriors code and having a concept of honour. This would put them at odds with the Cybermen who would view such concepts as illogical. It would also prevent them from submitting to full conversion.
This wouldn’t prevent Cybermen from taking advantage of their similarities. It stands to reason that they’d be able to convert the race with ease, a task made much easier if they can find Ice Warriors in stasis.
The player characters could arrive in a Martian tomb, only to be confronted by a guardian, awakened by the presence of intruders. Once the player characters have established they aren’t the ones to blame they could work with the Martian to prevent the Cybermen from creating a new breed of reptilian Cybermen.
Whether working together or against each other combining these alien races highlights the diversity of life that exists in a single solar system.
Bigger On The Inside 
I can understand why Terry Nation always refused to allow a Daleks vs Cybermen story. I’m sure he worried that his creations could be let down when placed next to another monster. I rather suspect, however, that the Cybermen would have looked the poorer in a joint story.