You could enhance that second point by adding some noise to the function so the difficulty isn't a smooth ramp — you get some tough monsters earlier and then maybe the next group isn't as difficult.
The basic process is:
1. Pick a random difficulty for the monster. 2. Pick n random locations for the monster and place it at the farthest one.
n is based on the monster's difficulty so stronger monsters get more chances to end up farther away. This means you can still run into really hard stuff early, it's just less common.