Crete sounds perfect. We were just there in early April and it is our favorite time to be there. Plenty open ( especially in the larger towns) , amazing wildflowers, history and great hiking. Enjoy.