I would suggest CO. While EWR has departure cues at heavy departure times, CO does a good job at accounting for this in their schedule. Result is that they usually arrive on time. While DL international service is reported as improved, I find CO to be consistantly good in Y as well as Business First.
I took CO EWR-EDI a few months ago and found it to be a good experience. Yes, we had to taxi for about 45 minutes before taking off from EWR, but that is not bad for both JFK and EWR during the evening rush. Cabin service was good in business first and the 757 is actually pretty comfortable in my opinion.