Empire Earth is a great RTS. The scope is crazy - you can go from guys throwing rocks all the way up to future mechs. I'm not sure if it supports random maps - I had more than enough fun playing the campaigns

Another game to check out is Age of Mythology. Unless I'm mistaken, it is by the same people who did Age of Empires. There is more emphasis on supernatural powers (calling meteor showers, earthquakes, malaria, etc.) instead of just regular combat - but still pretty fun.