The cheapest way to exchange money is to use a dedicate currency trading house. Your bank / credit card company will almost certainly charge you 2.5% on top of the exchange rate. I use XE Trade and pay half that.
I've never had a single problem with XE regardless of the method I used to move money — Draft, Wire, ACH, bill payment through online banking, etc.
It was free and pretty simple to sign up, all online — and besides the standard info all they required was for me to upload a scan of a bank statement.
The one problem is that it's easiest to have the converted money deposited in a bank account. If you don't have one in Euros then you'll need to get a bank draft (money order) and get it turned into cash when you're in Europe. You could also get it wired to something like Western Union but that has its own problems. There's a separate fee for both of these options, so it won't be worth it if you're only trading a small amount of money.
In short, I would recommend Joel's answer unless you have a bank account in Euros, in which case you should use XE or another service via ACH or EFT (no fee, delay of a couple days before your money is deposited). You could probably get an account on your first visit, depending on the particular country's laws or bank's rules about foreign account holders.