You can actually get travelers cheques in euros -- I know American Express issues them -- but I have never used them in Spain so I don't know how easy or difficult it would be to use them in a store or restaurant or elsewhere. I imagine in the larger stores (such as the department store El Corte Ingles) and tourist areas this would be more commonly accepted, but I really don't know. Maybe another board member has some input on that.
Some banks, such as Citibank, actually have many branches overseasm including Spain. You can withdraw money from their ATMs without any fees at all. And, other banks may have reciprocal agreements with foreign banks where you could use their ATMS without service fees. For example, your bank may have an agreement with the Spanish bank Caja de Madrid and you could use Caja de Madrid ATMs without service fees. I don't know how common this is, but it's possible.
As for the credit cards, I think it's too bad they are charging for foreign transactions because it's usually a pretty good exchange rate but it certainly seems to be the trend (mine went this way recently
). As CascadaDuSel mentioned, I have read about Capital One being a useful credit card to have abroad.
And, I would really recommend having 50 to 100 euros with you before you depart the States. Whenever I travel abroad, I order currency through my bank by calling them and they deduct the amount from my checking account. They ask me at which branch I'd like to pick it up and it's usually there the next day. (Give yourself some time before your departure date in case you plan to do this) If you have euros already with you it's one thing you don't have to worry about when you arrive. That way you don't have to hunt down a currency exchange or ATM immediately upon your arrival.