I don't know to what extent it's done in Borderlands as I've never followed it, but in Diablo 2 you're always going to find yourself getting to the same set pieces and such regardless of the random maps, but I like the sense of exploration (as long as there's no Iron Maiden spells being cast or a swarm of Willowisps). Even if your searching for the Durance of Hate level 3 or trying to find out which tomb is Tal Rasha's real tomb, it's a little different each time. That along with the drops and outfitting your character is what makes Diablo 2 so interesting for me and how you can go back and do the same quests over and over.
While I haven't had much experience with the Civilization series, another RTS game I've played like Age of Empires 2 would work as an example too and yes, random maps can be nice. Sure, you can have non-random maps as part of the game or user made (RPG or blood maps!), but I'd say that random maps can help promote strategy in regards to the environment you'll have to deal with on top of the strategy of winning the match.







