The Airport Shuttle is run by Gray Line. It's supposed to be every 20 minutes but knowing you are coming from JFK double or even triple the time.

I would go with the car or limo service.

What I do is take a cab. Now i can't remember the rule is if the cab is the flat rate of 35 dollars NOT including tolls and tip applies JFK-Midtown or going back.

Personally, I would fly into EWR.