Can't speak to reservations -- we were there ten years ago when there were far fewer RV's on the road and had no trouble finding somewhere to camp. These days? Wait for someone to chime in with current info.
I will say that it is prudent to expect to cover fewer miles each day as you will mostly be on two lane roads. We were there in June and there were lots of tractors and other AG equipment on the roads as well.
Hopefully since attended to, the loop road around PEI was rough (sees lots of traffic) but the interior roads (where you find most locals) were pretty good.
New Brunswick was my favorite place in Canada -- in 2007, St. John's was enjoying
1958 in U.S. Terms. Kids riding bikes in town, playing sand-lot baseball with nary a hovering parent in sight. Couples picnicking in the town square, soda shops (I swear). Also the nicest people on earth.
Enjoy