I would go for Lisbon. It has very good and cheap flight connections to the rest of Europe (not good to the West Coast of America). Easyjet, and RyanAir fly out of Lisbon, and the national airline TAP is very good and only slightly more expensive. Very nice weather. We still have not turned on the heating yet.

You can live cheaply and well. It may not be the cheapest cheapest in Europe, but is good value for money. For example at a restaurant opposite our office for only 5€ you can have a freshly grilled Sea Bass or a steak. Office rents are cheap as well. Expect to pay from 6€ to 10€ per m3. So you can out source the cooking and even the driving cheaply. A taxi to the airport will set you back just 8€.

Somebody I know just rented a two bed apartment in the centre of town for 440€ per month.

There is a vibrant Start Up Community. Some really good people.

For us the decision was more than just cost, but also standard of living.

You can find more details here in why we decided to open an office here: http://blog.webnographer.com/2010/10/an-rd-office-in-lisbon/