Age of Empires on the PC did indeed have random map generation. Age of Kings also included the scripting language that let modders create their own scripts to generate new types of procedural maps. The cells from the random generation were also repurposed as part of the pathing.

Most of the default scripts ensured balance by having a set of identical resources by each player's start. An example of the scripting language, placing a gold resource near the player start:

  create_object GOLD 
  { 
     number_of_objects 7 
     group_placement_radius 3 
     set_tight_grouping 
     set_gaia_object_only 
     set_place_for_every_player 
     min_distance_to_players 8 
     max_distance_to_players 14 
     min_distance_group_placement 4 
  }

if you can play different races or have different terrain abilities, symmetry is not the only balance issue