Everybody rails about the bugs here in MN, but really, they are not any worse than Maine or the Adirondack Mountains, and definitely not as bad as in NW Russia, Alaska or the NWT. In May you'll be ahead of the worst pests (other than tourists) the deer flies.
I am from northern NYS, but have lived in MN 26 years. There is a lot of beauty in this state, and it is GREAT for cycling. If I hadn't moved here, I'd probably still be a backpacker instead of a bikepacker. Our state parks have an "open to bikes, always" policy. If you arrive by bicycle, even if the campgrounds are full, we'll find a place for you to set up. (Yes, I am a state park ranger; bike patrol as a matter of fact.) Knutson Dam Campground is federal (USFS), not state, but is really nice. (I used to be a Backcountry Ranger on the Chippewa National Forest.)
You will like it here!