Traveling to Europe... what are my options for service?

Your verizon 5S and 6 Plus both are fully unlocked and can be used on any gsm carrier in the world.
Just go and purchase a prepaid sim card at the location you are traveling to and pick the amount of minutes and data package you want.
Prices, carriers options will vary by country so up to you to research and find out what is the best bang for your dollar at the location you are staying.
Not sure if packages that you buy from certain carriers would be international or only valid for use on the country you buy them at.
Many many variables depending on what you want and what is available on those 3-4 countries you will be visiting.

I'll be interested also to see what folks say. The last time I went to the UK I got a giffgaff SIM and the experience was pretty horrible for data.

I think next time I'll go with "Three" (three.co.uk) as I read good things about them. Not sure if they have any coverage outside the UK.

From what I remember, SIMs that work across borders seemed to be quite a bit more expensive than changing from country to country. Might be worth it for you, though.

You probably already know that your US carrier will rob you for worldwide coverage.

You can purchase a local SIM from each country you visit, or purchase one that works across all of them from Telestial or Cellularabroad. I purchased local SIM's in several different European countries last year and it became kind of pricey.

Starting this year, throughout the EU, roaming is being cut in half and by 2016 it should be eliminated. So in theory, if you purchase one local SIM, it should be the same throughout the EU (although I will believe it when I see it in practice).