A milestone is achieved AFTER the second encounter, after a long rest. In other words it becomes available during the short rest, following that second encounter, and can be used in the THIRD encounter after a long rest.
This should be a flexible rule though. I've taken to giving it after a difficult encounter, rather than robotically giving milestones after the second encounter. My players have just been sailing through encounters, as a result of a Striker heavy group, optimization, and the use of a Pacifist Cleric. Sometimes they won't hit a milestone until the FOURTH encounter, after a long rest.
Um, after a long rest your Action Points always reset to 1.

An EL+4 encounter should give an AP right away, and Easy encounters (EL-1 or below) generate milestones more slowly, or not at all, per DMG.
Also, you don't get them for resting. You get them for completing the encounter. Technically you could get an AP without having short-rested at the end of an encounter. You might want to do that to preserve temp hps or another benefit.