(I will use Europe as an example, but I will build in stopover/open jaw opportunities and use Hawaii as an example of how you can stretch your miles on a Europe award.)

For Europe:

AA
Off peak (Oct 15-May 15) Coach: 40K miles roundtrip
Peak (May 16-Oct 14) Coach: 60K miles roundtrip
Business, all times: 100K miles roundtrip

Note that you can book one ways for half of what I quoted above, and you can include a stopover (in an international gateway city) on each one way award. This means, for example, you can fly HNL-JFK (stopover)-Europe for 20K each way, just as you can only fly JFK-Europe for the same 20K.

AA has pretty good availability to Europe on its own metal, and also note that it has several partners (such as Iberia, Finnair and Air Berlin) that also could work if AA lacks availability on its own metal. I've left out British Airways due to its prohibitive fuel surcharges, but have in mind that if the surcharges work for you, they have good availability as well.

AA Award Chart

DL
Coach: 60K miles roundtrip
Business: 100K miles roundtrip

Delta does not allow one way bookings, but you have the flexibility of booking a stopover AND an open jaw on a round trip ticket. For example, you could book JFK-AMS(stopover)-IST (destination)-CDG-LAX for 60K in Coach (granted, this may not be the best example, because availability is likely tough on CDG-LAX, based on what I've read, but you get my drift). You also could feasibly have an itinerary like JFK-AMS (destination)-JFK (stopover)-SFO for 60K, or even JFK-AMS (destination)-JFK (stopover)-SEA-HNL for 65K (reprices 2nd leg as Hawaii-Europe costs more in miles). Note that to have any chance of flying to Hawaii on a Delta award, you'll probably need to fly on partner Alaska Airlines (I believe their product is excellent, by the way). You can use their website to find availability.

Delta does not have great availability, in general, on its own metal, especially in business class, but fortunately for Europe redemptions, they partner with Air France and KLM (among others that fly to Europe from JFK, such as Alitalia and Air Europa (note that I'm not familiar offhand if DL adds major fuel surcharges for one or both of those)), both of which have good award availability.

Delta Award Chart

UA
Coach: 60K roundtrip
Business: 100K roundtrip

United has some major flexibility with award bookings as well. United also allows one way bookings. United also has the stopover and open jaw opportunity. You can do a similar itinerary (with different likely routes, of course) to the DL itinerary above that adds HNL for only 62.5K total, so only 2.5K more than a normal roundtrip to Europe.

United has a great website that will allow you to book so many award combos. And Star Alliance is extremely well connected for Europe (and across other parts of the globe). For these reasons, UA miles are quite valuable.

United Award Chart

Overall (re: your travel plans), I still think AA or DL would be the way to go for you because they provide upgrade opportunity for high level elites, and are well connected from your presumed preferred airports of LGA and JFK (though I don't have confirmation on this- is EWR better for you? The same?). Skymiles are lame, but they can be redeemed if you know what you're doing. Still, I'd have recommended UA over DL (for the ease of redemption alone) if there were any legitimate chance at regular upgrades on their flights to LAX.

I am drafting another post regarding how I might take it from here if I were you. May take me a while, though. Busy for the next few days.