One of the problems I have had with internet cafes in European ports is that they have European keyboards -- and it's amazing how exchanging even two keys (and relatively uncommon letters at that) slows down my entry speed!

If you have your laptop with you, lots of European coffee shops and fast food places are beginning to offer free access.