Apply for iEAD, on-line
Its really fast and simple.
You could get your card within 30 days. If not, you can go to a local office, show the receipt (which you print on-line) and get an interim EAD.
I applied for one last week (renewal of EAD) and it was a breeze. However, yet to receive the card.
My 2 cents.