We want to go to North-Eastern Mediterranean (Greece, Croatia, maybe Montenegro) next August. We would like to book hotels in advance, to get better prices and wider choice. However, it is obvious that booking, for example, now is too early. When it is optimal time to book hotels in advance?
Seem like general hotel booking rules apply here too:
Book as early as possible (as soon as you know the schedule). Now is NOT "too early". You will get better availability. The only exception is if there are NO hotels which you can book with free cancellation. You will get better availability. You might also get better pricing too (mostly because good and cheaper hotels are booked early).
Book with free cancellation, of course - even if you have to pay premium. It might still be possible to book into non-refundable rate within a week before checkin (depending on how busy they are);
Check the prices and availability periodically (especially in last two weeks), and check the reviews too periodically (especially recent). New hotels might open right before the tourist season starts. New reviews might indicate your chosen hotel is turning into a dump.
If you are unsure between two nice hotels, book both for the same dates and decide later based on above.
If you're unsure about dates (i.e. whether you gonna stay in that city for 3 or 4 days), then make several separate bookings, each for one day if needed. Some websites (Orbitz, for example) do not allow reservation modifications, only cancellation.
For a more specific answer you might want to provide exact dates and cities (booking in Santorini in June is a bit different from booking in Athens in December), but even there I don't see anything specific or why the rules above wouldn't apply.