Make Locations Evolve with the Player
As a player, I particularly enjoy the game when my actions affect the world (or if I'm presented with an illusion of it). I would come back to the locations I've been in before and meet new characters or seek other significant changes. Nothing in the world should stay the same, static throughout the player's walkthrough. Make the old location feel like a new one, but still remain more or less the same place, and your players will love it. It's in human nature, to come back to the places we've been to and see how they changed.
A decent example of this is Pillars of Eternity. Throughout the playthrough some locations change, new characters and questlines appear, new buildings arise or fall, and players are interested in coming back and exploring again. For instance, Raedric's Castle, which (spoilers)
can be cleared by the player, but later in the game the King would return in a form of an undead and retake the castle, slaughtering everyone in the way and raising them to serve in his army.
When the locations never change, and players come back to them only to feel like they've gone back in time, it hurts immersion. For example, the starting town in Neverwinter Nights 2 doesn't change at all during the first stage of the playthrough (which, in in-game time, should take at least a couple weeks). When the players come back to visit and expect the villagers to have rebuilt the town and try to recover, they're greeted with the same town on fire and scared townsfolk they left. Frustrated, they leave to never come back again, feeling like they've been robbed of an potentially interesting experience.