I have had about 5 early [6:00am - 6:45am] departures at Newark Terminal C since 9/11 - never any backup whatsoever. I always use the largest security entrance near the new gate 130s concourse.

I have also taken a few Northwest flights at those times. Security is somewhat slower, but was not a significant delay. 1 hour ahead was plenty.