Stayed last year at Big Eddy in the Katahdin area (on Golden Road), loved it.
http://www.bigeddy.org/

This is a good thread, does anyone have any recommendations for the southern portion of the State? Lets say from Lewiston down?