1. There be multiple borderland maps that are on rotation, so that every border land is different, with up to 6 (and hopefully more) borderlands that could be selected.
2. Make one of those maps a Wild West theme, complete with tumbel weeds, cactus, horses with no names, and music from A Fist Full of Dollars.
3. Add environmental effects such as earthquakes, tornadoes, fires, etc.