In reply to mgce25c:
I always enjoy a day over in Telendos (home to the best crag Llambda) and we have often thought about staying on the island. You're away from the bustle of Massouri but only a short boat trip across to Kalymnos. Can't personally vouch for the accommodation but it might fit what you're after. Found this
http://telendos.org/ which leads you to a place called On The Rocks. There are other places there too, and a hotel called Porto Potha which might be a bit more up market. [
http://www.telendoshotel.gr/
Congratulations, and have a great trip
Andy