A random map is procedurally generated by a .js file calling upon a random-map-library. A scenario or skirmish map is created in the Scenario Editor, and is static, unable to be edited. I know that it is an option in the Scenario Editor to generate a random map, then save it as a Skirmish or Scenario map, and that a few people have written random map scripts to recreate scenario and skirmish maps as random maps.
Assuming the RC is same as release 0.28 git branch :
Germans are now unplayable
Stone gather rates is almost doubled compared to xml template for seemingly all units
Last known bug for Germans i noticed and don't think got fixed (can't check cause can't play them): Fertility festival and loom become available in wagons after researching Migratory Resettlement. Don't think that is intentional.
I've read some explanation here in the forums, and there's mouseovers where you select the map type in the game. Basically Random maps are generated procedurally while the others are of static design? I don't really know.