My boss went to Mykonos last year. He wished that he had gone there before he was married. Looking at his photos I can see why.
My wife and I spent our honeymoon in Greece, and we visited a couple of the islands. Our favorite was Corfu. We made arrangements with a travel office in Athens to lease a bungalow on the beach of Corfu with a small jeep-like vehicle included. We drove that little jitney all over the island and had a great time. We never were bothered by anyone and there were no crowds at any village or on the beaches. The game plan was to sort out our trip after we got to Greece. My new bride was very nervous about arriving in Athens with a booking for only two days in a low-priced hotel and no other plans, but we managed just fine. Of course, that was twenty years ago, so things may have changed drastically in the current world situation.
I went to Crete a few years ago. Great place as long as you avoid my fellow countrymen (hordes of obnoxious Brits) in the resort towns. Rent a car and travel all over - the central plateau is stunning; the food and drink are good; the beaches are great - some topless, some nude - the archaeology is fascinating.