Hey Wayne,
We travel Newfoundland like you are thinking but we mostly boondocks maybe one or two campgrounds in two months...or not.
You MAY need reservations for ferry on the way back but we have never made them but do call ahead to see what is available. But make them if you wish.
We don't like crowds either and have the place to ourselves in May/June. Provincial parks are great and a source for laundry/dumping but it is cold...be prepared for that and the mountains could have snow in May. STILL a great time to be there.
We did hit bad mosquitos one time in June/mid but we just moved on to another area or more breezy area. I think you plan is solid.
Donna and David
And we are part of boondockers welcome so you can stay at our house if you need to on the way out!