20 Euros will get you a phone with 5 Euros pre-loaded. At .30/min it's comparable (if you put 15 Euros additional on the phone, bringing total cost to 35, you get ~65 minutes). This is w/ Vodafone anyway, though I imagine others are similar.
edit: so why the rush to get the phone beforehand? Just walk into a store and grab one.