May can be cold and wet at the same time.
It's a crap shoot, you could have glorious weather, or be riding into a stiff wind
and a cold driving rain.
If you can wait to late May, that would help.
I have bike toured Maine more times than I can remember.
If you want some suggestions, be glad to help.
For example, I think one of Rabo's pictures is of the Lake House Inn in Waterford.
We stayed there and loved it.
I'd also suggest taking a day off in Camden. It's perfect for it.
The town is walkable, there's a cheap motel, good restaurants,
and a market in town center with excellent fruit. There is also a bike shop just south of town.
If you get up early, climb Mt Battie (mountain is not accurate, it's 600 feet and the trail only takes a few minutes)
and watch the morning mist rise up from the bay.
You need to leave Camden using backroads if headed North, that's tricky, so if you wind up doing that, we can go over it.
Last year we cycled down the Schoodic Peninsula, which is just past Acadia, and that was very nice.
From there we took the ferry over to Acadia.
Lots to chose from.