I'm not sure of the earliest time but I have a PS for Tony's breakfast on Wednesday, 11/13 at 8:10 am. The Disney web site says the park opens at 9 am that day.
I got a PS for Tony's at 8:05 November 18....my question is how do you manage to get into the park on time if the monorail isn't running until 8? Did you park at the Contemporary and walk in?