Congratulations!
NS, NB, PEI, NL...all great for a honeymoon.
My only reservation is your timing. It is still cold & rainy in those provinces in May, even late May.

Is there any way you can go later in the season? July-early October would be optimum times. I was in Cape Breton the first week in June, 2012(i.e., 2 months ago) & it was cold & rainy the entire week. Miserable weather.

I am partial to Cape Breton(Cabot Trail) for its spectacular beauty. PEI is great for cycling & beaches.
I know NS & PEI better than NB & NL.

OB1

Hi OB1!

Thanks so much for the response! We aren't too concerned about the weather. We're getting married in Northern Wisconsin (US and a very cold place) near the end of March and want to take our trip while the weather is still shifting. We'd also really like to take advantage of early/pre-season rates as well...without stuff being still closed. We are very much winter-folk, thus the late Winter wedding!

Have you been to Quebec City?

-Katie

Wow...ten days to do all that...but if you are looking for NB or NFLD I have to say NFLD by your description of loving to hike etc.

I loved NFLD but choose east or west...you won't have time for both

Now for a completely different idea. If you are set on Quebec City and only have 10 days altogether, consider staying in the province of Quebec and going east towards Tadoussac where there is a beautiful fiord and whale watching. Rent a car, head east from Quebec City 45 minutes staying in Baie St. Paul, great food etc. With that as a base, northeast of there is Les Haute Gorge provincial park where there is excellent hiking and climbing. I was quoted in a recent Fodor update of the area. It's amazing up there.
Bring your French/English dictionary!

Personally with 10 days I think Quebec City and PEI and Cape Breton and NFLD is not doable unless you have a private plane.

Thanks for the advice MsLizzy. I should have been more clear that we are trying to choose between either the Quebec/NB/NS trip or Newfoundland. I wish we could do it all but alas, as soon to be newlyweds our funds will be limited.

Well that is a difficult choice but luckily you have the future to look forward to.

I absolutely loved Nfld and spent 2 weeks on the eastern side landing in St. John, The Avalon penninsula and driving to Bonavista, Trinity will satisfy your northern European sensibilities (I was born in Holland)

I'm sure you will love whatever you decide. Even QC to Cape Breton is a lot to do. Both being amazing destinations.

If your into the outdoors, then Newfoundland is a great place to go, especially in and around Gros Morne National Park...the hiking and scenery there is spectacular. However, May might be just a little bit early as there could still be some snow in higher elevations...