Options would be easy and tons of volume, just call up your bank's FX desk and they should quote you on $500k cash options;
Of course you could buy the options yourself against the EUR/USD futures; each futures contract is for $125k so four lots would give you a very accurate match.
You could buy a 1.10 Call on four lots with a DEC16 expiry.
Alternatively, based on your post, an alternative to just buying the calls to protect you against a EUR rally, you could actually sell four PUTS below the current market;
So, say you sold a 1.05 PUT for DEC16 expiry, this would essentially guarantee that your 500k would be converted at 1.05 if EURUSD is trading below that level come DEC16; selling these PUTS will generate income for you which you keep, regardless of price action. The downside to selling the puts is that that income you generate on selling them is all that you can make, there's no more profit, so if the EURUSD rallies to 1.20 the only hedge you have is the income from selling the puts.
Thus, and hopefully this is all still reasonably clear, you could sell four puts down at 1.05 and use that income to buy four lots of 1.15 calls -- this should be close to netting out your costs though I'd have to check the prices, meaning you should have a pretty cheap hedge.
Any reasonable FX broker could do this for you and it really shouldn't be too expensive at all.
EDIT:
Just to add; indicative pricing; market quiet at the moment so only looking out to MAY16 expiry:
If you sold four 1.05 puts you'd make 40 ticks per contract, which is $12.50 * 4 contracts * 40 ticks = $2,000 (you keep that no matter what, but you commit to change your Dollars at 1.05 if the market hits there before MAY 6th);
You could use that $2,000 to buy four lots of 1.16 calls; thus hedging you entirely from 1.16 and higher between now and May 6th