Being a cell phone salesman, I thought I'd get my 2 cents in here.
Buying the phone in Spain and using the recharge airtime is definately the cheapest way to go for a cell phone. Do not rent one out from here. Even renting from someone over there isn't always your best option.

Voicestream has a couple of models that will work for you in Spain. The Ericsson T28 is a great phone that will work in Spain. The cheapest option is to use it with prepaid cards you buy there. Plus it's a phone that you can use back in the US in most major cities.

Good luck.