There should be an entry in the topmost menu to immediately start a completely random single player skirmish.
So you can start the game, make one click and *zoom* you find yourself playing a random match.
Things that should be randomized:
Map
Player number/location
Number of AI opponents (tendency towards the maps maximum number)
Difficulty of each AI (tendency towards "hard")
Position of each AI (empty slots shouldn't always be on the same positions on the maps)
Things that are not that important for this to work nicely:
Teams (low probability)
Player color (maybe there should be some preset in the settings,so a player can always have his favorite color)
Things that should not be random:
Power level should be fixed at high (so a match will at least not be that frustrating, if everything else sucks)
No bases (so players can be creative)
Scavengers (There should always be Scavengers when supported by a map)
No structure limits (because if just one technology (e.g. Hover or VTOL) works on a certain map, it shouldn't be disabled)
The difficulty and number of opponents should not be randomised as you suggest. Someone wanting to play a random skirmish should be able to set it to their level of skill.
My suggestion would be to assign a points value to each difficulty level, that must add up to a user-set value. So someone wanting a 50 difficulty game could be set against two 25-point enemies or five 10-point enemies.