I wouldn't go much earlier than 12:30, with 1pm being a better idea. Granted, once you book an early afternoon flight you'll probably get to the airport by 9 and could have made a 10am flight, but it is a great risk. Murphy's Law has a way of popping up in situations like that, and if you had a 10am flight some problem would develop and you'd miss it.
Last summer while leaving the ship in Miami the Immigration computers suddenly crashed and they halted debarkation for something like 45 minutes. This screwed many passengers who had early flights - and from Miami airport which is just a few minutes away.