Hay varios temas en los que se habla de cómo es más recomendable hacer los cambios de dinero. Echadles un ojo que seguro que quedan resueltas vuestras dudas.
De todos modos, depende de cuánto dinero vayais a cambiar. Yo lo que haría sería llevar una tarjeta de crédito, y sacar dinero de los cajeros cuando haga falta, en cantidades no inferiores a 400 zl (más o menos, 100 euros). Así la comisión que se paga en el cajero no se nota tanto.
Si lleváis euros, id a cambiarlos al banco, que es lo más seguro y más barato. Comparad precios de todas maneras.
Saludos.