I'd recommend early June over Mid-May by 10 to 1.  the earlier you go, the fewer bugs, but the weather is more likely to be nasty as not.
Bad weather typically comes out of the NE or E, nicer weather from the W or NW - so you can count on winds form those directions depending on how the weather is.  In that last week of May/ 1st week of June time frame, you can typically expect to have a morning or two with frost.  Day before Memorial Day 2008, there was 4" of snow on the road between Thunder Bay and Atikokan - it snowed at Dawson Cr campground, and it was 20 degrees the next morning.  Normally, there will be a mix of bad and good weather - just depends on your luck.


I've only started a trip in Mid-May (12th) once - I decided that was a lot too early, and mostly go about the first week in June, and now usually try to take in Memorial Day to save a vacation day for me.  Even that time frame can be cold and wet - Just read some of the trip reports on here, and you can see that.

As far as solitude, that is relative.  At the end of May early June timeframe, I'll not normally see many people - one or two parties a day, and 2 or 3 days where I'll see nobody else at all.  To see fewer people than that, you will have to get off the beaten path more - take a portage into a dead-end lake, or camp in some remote back bay.  

Jesse and Maria Lakes tend to have several camps, all in close proximity - I'd avoid camping on them if that is going to bother you.  Most of the larger lakes have enough islands and back bays that you can be away from the flow of traffic when you camp.

If you want a route suggestion, I'd say start on Beaverhouse, and then go into Quetico Lake.  That is a big lake and wind can/will be an issue, but it is relatively easy to "get away" from the main travel routes and feel more secluded.  You will be/should be about halfway down the lake at the end of your first day.  From there, well ?

It depends on what you want to do - if you like moving camp every day and seeing some country, you could head down into Jean, do your layover day there, and then return back thru Quetico L.

6 days (5 nights ?) is not that long a time to do "everything".  With one layover day, that leaves you about 2 days for "in" and 2 days for "out".  A typical full day's travel, with maybe 3 or 4 portages will cover somewhere between 12 and 15 miles, depending on how hard you want to work, and how much you have to fight the wind.  That's mainly why I recommended going into Quetico Lake - good fishing, some of the better pictos in the park (in the Northern arm), lots of good camping, and not much portaging.  If you want to see more country, you can portage one or two lakes out from Quetico, or not.

Bugs at that time of year are really weather dependent.  Usually, not too bad - its before the main black fly season, and mosquitos aren't too heavy either.  Ticks can be an issue, and I think they tend to be worse in the NW quadrant of Quetico than in the other areas - you just need to be aware that they may be out in force, and do a "tick check" every so often.  Ticks are worst on the portages than in camp, but they do like to hide in the pine needle duff.  

My fav bug dope is geting impossible to find. I've always had good performance from Cutter's Creme - not a real high concentration of deet, but it dosen't melt plastic like higher deet can do.

The tip on a pump spray bottle is a good one (you can always take the top off and use the liquid - can't do that if a spray can stops working) - I will either bring a pump spray bottle, or a normal pressureized spray can, and spray the hell out of my hat brim if the bugs are bad, and my sleeves around the wrist, especailly before the start of a protage - that tends to keep them away from my face - I never bother using a head net, but I do bring one just in case I ever really need one.  If you have a heavy canvas shirt, or an average thickness fleece jacket, the mosquitos can't bite you in the middle of the back - I always plan on wearing that heavier shirt as a light jacket for that reason.

If you look at the top of the "general..." forum, you'll find a "The Hot Spot - best of threads" postiing - take the time to read that - lot of good info collected there  and look at the trip reports dated in the timeframe you are considering, to get a better feel for general conditions at that time.