Random maps are too complex for the meantime. However, I should note that most of these random maps you know aren't truly random (I've only tried 2 games with random maps to be honest, that I remember, Civ4 and AoE2). They work by using a script to tell how to make the random map, and to be frank, it's not easy (My first 5 or so attempts to make a very basic map produced laughably bad, unplayable games). For the most part, tilesets add that feeling of difference that "random" maps were meant to do. Plus, Glest has so many different maps available that it adds up. For the most part, a random tileset would be a better and much easier alternative to random maps, since the maps can feel quite different. As well, random rotation of the maps change things too. We already have random starting locations, combine that with different tilesets and for most players, the maps feel different every time.
Random textures would be fine, since you could just add a few very minor details to an alternative texture for very little work (ie: change the hue, add a scar, etc) to give the feeling of individuality among units.
Random models would be fun, since, like the textures, you could add a minor difference that wouldn't take a long time to model/animate and could yet add notable changes. For example, having units do different actions for their stop animation could be interesting.
Random teams isn't a good idea, since the best team maps partner players up with their teammate, which wouldn't work with random teams...
Random events....meh.
Random techs are already available.
Random hit points is pointless really. Weaker units shouldn't beat stronger ones by rushing, but by proper strategies and command. The ability to deal "random" damage already exists though.