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]
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.
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:
I can think of AoE and Worms on the PC, and i enjoyed both of these tremendously.