Brogue[1] is an acclaimed roguelike that follows in the tradition of substantial procedural content for that genre, and exists on IOS[2], at least. You might find others at: [3]

[1] https://sites.google.com/site/broguegame/

[2] https://itunes.apple.com/us/app/brogue/id613921309?mt=8

[3] http://forums.roguetemple.com/index.php?topic=3697.0

Minecraft at a minimum uses a variant of perlin noise for the terrain generation.

Also, while it doesn't have the replay value found in the Minecraft sandbox, Starbound procedurally generates not only the map/terrain but also the mobs.

http://en.wikipedia.org/wiki/Starbound

My personal favorite is Pixel Dungeon, which was the best rogue-like on mobile i could find

Minecraft. The whole 3d world is generated proceduraly.

Most one-runners do this to keep the gameplay fresh and unpredictable (tiny wings, canabalt, temple run)

did AoE really use procedural generation? it could have been due to the immaturity of the genre, but i think you'd be hard pressed to procedurally generate balanced RTS maps. seems more forgivable for something like Worms, but still kind of dangerous.

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