Crete Itinerary

Its not a bad plan but I would make a couple of tweaks.
Day 1 good
Heraklion https://www.flickr.com/photos/stanbr54/sets/72157655935354556

Day 2 get to Knossos early before it gets crowded. You may want to take in the Archeological museum where the stuff from Knossis is displayed. Are you renting a car? There is a good bus system KTEL which is inexpensive and frequent to Rethymnon. Do try to find a hotel in the old town area.
Rethymnon https://www.flickr.com/photos/stanbr54/sets/72157654700502270

Day 3. I don't think you will have sufficient time to visit the Fortezza on day 2 so this is a good opportunity for you to do this great site. Provided of course that you might be interested in a well preserved Venetian fortress. Its a good 4 hours to visit the fortezza.
Assuming you have rented a car you can visit a couple of villages on the way to Chania or perhaps Ancient Aptera. I would not head to Balos for that evening. Get to Chania and make it your base for the rest of your stay. Chania will take at least 2 days to fully explore.
Chania http://www.flickr.com/photos/stanbr54/sets/72157632117917828/
Chania May 2016 https://www.flickr.com/photos/stanbr54/albums/72157671465596275

Day 4 and 5. I would reverse them. Do Samaria first. It is a long day. You will depart Chania around 7am and arrive back around 7:30 Pm after hiking 16 kilometers.

Samaria Gorge hike the easy way. https://www.flickr.com/photos/stanbr54/albums/72157670610409530

Most people plan a down day after the gorge. That would be a good time to do Balos. There is a boat excursion from Kisamos about 45 minutes from Chania. You can drive or take the bus. This excursion gives you a pirate fortress to climb up to and two lovely beaches. You will be gone from 9am to 6pm but its a relaxing day.
Western Crete http://www.flickr.com/photos/stanbr54/sets/72157632115757899/

Aptera images 38-62 Balos Gramovossa images 79-106

Day 6 you can take the bus to Elafonissi or drive it or if you have not finished exploring Chania just stay and relax and enjoy this vibrant city.

Thank you so much for your great advice. We will have a car. A few more questions, please....

1. Day 1 and 2 are good. Confirming that 1/2 day in Rethymno is good enough or should we stay morning of day 3?

2. Day 3. Since we have a car, we do not mind driving anywhere (S,SE, SW) in central Crete since to visit mountain villages and beaches. http://www.we-love-crete.com/villages-of-crete.html and http://www.we-love-crete.com/crete-beaches.html
   Do you have any recommendations?
   We can also stay in Rethymno that day 3 if needed which would mean we would change Samaria Gorge on Day 5?

3. Day 4 Samaria Gorge and Day 5 and 6 for beaches. Do you suggest any other beaches/villages near Elafonisi and Balos that we can visit along the way?

Thank you again for your great and detailed ideas. We will surely use your advice. Btw...your photos are beautiful and inspirational!

The primary place to start the Gorge trip is from Chania so you will need to be there the night before and the night of the Gorge hike.

So after Rethymnon on day 3 if you have not seen the Fortezza morning will be a good opportunity. But you should be in Chania that night. You can stop at Ancient Aptera on the way to Chania. There are little mountain villages in this area. Or just get to Chania and enjoy it.

Day 4 do the Gorge.

Day 5 Do Balos and Gramovossa rest. You could drive to Paleochora after the excursion and spend the night in this village. Next day 6 take the day boat to Elafonissi return to Palechora for the evening. Then drive back to Chania on the morning of day 7. Or you could return to Chania after balos Gramovossa and do Elafonissi from Chania on day 6. That puts you back in Chania if you have an early flight out on day 7.

Or a radical change to your plans. Skip Rethymnon entirely and do a night in Chania (you will kick yourselves if you miss Chania) Thats day 3. Day 4 do the Balos Gramovossa excursion then drive to Palechora and enjoy this lovely little town. Day 5 take the early morning bus from Paleochora to the top of the Gorge and do the Gorge. Take the ferry back to Paleochora and spend the night there. Day 6 take the day boat to Elafonissi for rest, overnight in Palechora. Day 7 back to Chania for your flight out.

Is there no way for you to add a couple of days to Crete?

thank you standbr for your excellent advice. I believe I will do your first recommendation. This would give is days at beach and early evenings for Chania. On day 3, we will try to visit villages on way to Chania but also have time to see Chania when we arrive that day.