The best sunset views in Paros are from Parikia especially during the time of summer when the sun sets between the Portes Rocks. Naousa is however the Paros hotspot for staying. I would recommend you also look into Antiparos for staying. Antiparos and Paros can be considered as one island since there are multiple 5' ferry crossings per day even until late at night. You cross to Antiparos from Paros at Pounta with frequent bus connections to Parikia. Wind is all over the Cyclades.

Naxos, or Paros and Antiparos are close and would round out your experience nicely. I'd go with Paros and rent a scooter to take over to Antiparos on the frequent little car ferry from the secondary port of Pounta and go up the mountain to see the cavern. It's very interesting and traffic is very light all over the island. Then you can stop at Apandima Beach for a swim before returning to Antiparos Village for lunch. Scooters make exploring both islands a lot more fun and traffic on Paros isn't at all heavy once you're out of Parikia, the main village.
Hello!!!
Some of the best family-friendly islands in Greece are:
Paros- Various activities, safe waters, beautiful mountain villages with friendly locals, yoga centres, excellent food and healthy products and endless choices for kids to play safe and enjoy their holidays. Very well organised island without the hustle and bustle of a massive touristic destination. Learn to do windsurfing or SUP with your kids, enjoy sailing with small or big sailing boats, chose one of the various kids gardens and play schools all year round and be carefree and relaxed on the beach with a smoothie or a light cocktail while your kids play safe close to you. Paros is a family friendly island and the weather starts to get warm from April so you can visit it earlier in spring or autumn which are both very good choices if you want to avoid the peak of the summer season in July and August. Paros can also be combined with Antiparos, Naxos, Ios, Santorini and Mykonos in case you are into Greek Island Hopping.
Antiparos- a very quiet island, high quality accommodation and restaurants, crystal clear waters and safe beaches for kids and adults and it is ideal for family holidays in Greece. You can reach the island of Antiparos from Paros (there is a small boat to Antiparos on a daily basis). There are not too many hotels and rooms for rent on the island so if you leave everything for the last minute you might find some difficulties to find what you want.
Naxos- one of the most family-friendly islands in Cyclades. Archaeological sites and beautiful villages, family-friendly beaches, with soft sand, shallow waters, all touristic facilities and water-sports.
Amorgos- became famous when the French director Luc Besson filmed the movie "Deep Blue" back in 1988.
It is an unspoiled island in Cyclades. It will surprise you with its tranquility and relaxed atmosphere. The locals are super friendly and the quality of food is very high. The monastery of Hozioviotissa is a unique sight that you must see when you visit the island. Even in the summer season you will find your peace of mind because it is never crowded! Try to find and participate in one of the many local fiestas and events, it will surely be a unique experience!
Crete- Greece’s largest island, located in the southern part of the Aegean Sea. Crete is one of Europe’s earliest civilizations and has everything form fine-sand beaches, to the White Mountains. The tallest of the mountains, Mt Ida, is home to the Ideon cave, which was the birthplace of Zeus. Aside from beach lounging, and aquarium going you can expect to take in the Archaeological Museum in Iraklion, housing Minoan artifacts, and a Bronze Age settlement, called Knossos. Crete has family-oriented resorts, 3-star hotels, and guesthouses all over the island either within seafront or mountain views. Make sure that you join the Countryside, Wine, or Renaissance festival during your visit :)
Spetses- Picturesque and close to Athens and Piraeus port. Beautiful Greek island full of green trees and fresh air. Its unique architecture will amaze you and the fact that cars are not allowed in the center of the island make it the perfect choice for small or older kids ;) Everything is accessible on foot, the restaurants and taverns serve excellent fresh food, literally the catch of the day, the apartments for rent and the hotels offer very nice accommodation and the beaches around the island are super nice and gorgeous all year round. It is also close to the islands of Hydra and Poros so you can combine your holidays with a little bit of Greek island hopping.
Zakynthos- Zante has many beaches. Olive and fruit groves surround the impressive Venetian works of architecture. You will fill your days enjoying the azure waters, and learning how to protect the loggerhead sea turtles at the Marine Park, as well as day-trips to tiny cliff-top hamlets to catch the sunset... There are lots of well-organized resorts, in rooms, seafront hotel, and two rent-able windmills!!
Lefkada- a top water-sports destination in Greece. Kitesurf, windsurf and diving are only some of the activities you can do with your children. Lefkada Town has also many cafés and bars that your teens will love. Lefkada is an island but you can get there by car because it is connected to mainland Greece with a bridge!! This is important if you travel with your kids as it is a cheaper option than the ferry and it is also more convenient by carrying your stuff.
Rhodes- an astonishing island with wonderful beaches, traditional towns, like Lindos and the Medieval Rhodes Town, as well as big modern hotels, with all-inclusive packages, where everything is on your doorstep. Water-sports facilities, restaurants, cafés, wellness centres and everything you need just to switch off and relax.
Kos- there are many all-inclusive hotels and top things to do and see, like ancient monuments and vivid nightlife, which is perfect if you have teens in your family. All beaches of Kos are sandy and organised, so you can relax without having to worry about anything.
Samos- an ideal island for families thanks to its long, sandy, organised beaches with crystal waters as well as the low prices in accommodation and food.
Chios - beautiful, well-preserved villages of the island, and your kids will love the traditional sweets, the orchards and the mastic trees, which are everywhere on the island.

Antiparos is busy in midseason, that I know, only going to be worse in August.
The ones you are looking at are possibilities as are Kythnos, Serifos, Sifnos, however those are popular with Greek tourists.
Others might be Kos on the NW coast, between Mastichari and Tigaki, hotel building is increasing in the area which may make some parts crowded.
Samos - west of Pythagorion towards Ireon is one continuous beach, not the greatest, but about 5 Km long but with accommodation at each end so you just walk...
Ikaria - the wind swept north coast between Armenistis and Evdilos.
Skyros - the beach from Magazia to Molos just below Chora, it might be popular with Greeks in August not sure about that point.
Rhodes is a possibility though there is extensive all encompassing tourism. The wind blows people off the west coast beaches so those don't get crowded.
I'm a throw down towel person, and hate sunbeds crowding out beaches. Those with sunbeds tend to be the most crowded for economic reasons.
Small islands with small beaches tend to get crowded very easily with high season.
All the Cyclades islands are subject to the Meltemi wind, bit less in most of the Dodecanese islands, but still present.

When are you going (affects crowds & heat) ? And will you rent a car at all? Actually, I think the best for the 2 of you would be Naxos and ANTIparos ... both have wonderful beaches that are walkable, in Antiparos ... and Naxos is great for St. George beach adjacent to town, for kids under 9 ... shallow & safe and clean... Antiparos has charm galore, and y ou have best of both worlds... y ou can explore the Town of Parikia on Paros, and Antiparos is just a 10-minute ferry ride or a 30 minute ferry, depending on whre you start from. In Addition, This excurison company .operating from both Paros & Naxos - http://visit-cyclades.com/day-cruises/naxos-cruises - has interesting day sails to explore. Here are some great photos by my friend "stanbr" who is, like me a fan of both islands --
ANTIPAROS - https://www.flickr.com/photos/stanbr54/sets/72157632126687570/
TRIP around NAXOS - https://www.flickr.com/photos/stanbr54/albums/72157634605629689
NAXOS TOWN - https://www.flickr.com/photos/stanbr54/sets/72157632094558042/
SIFNOS is another possibility ... beaches like Vathy are quite nice, bus system is pretty good ... port town not as interesting -- people are attracted to Sifnos for its many hiking possibilities ... SERIFOS has a splendid beach, with only 2 places on it (Coralli Bungalows and Vassilis Guesthouse), port town is v. small ... it's a wonderful 3-day visit AMORGOS, again, has a delightful beach. Aegali (tiny village) and several good places to stay on it, again, it's a 3-day visit ... FOLEGANDROS has a completely enchanting "high town" where one stays .. but beaches are hard to access & not terrific. MILOS has 22 beaches, many of them w. no "facilities" and a fun round-the-island boat excursion -- car is almost mandatory, bus system limited.
But you know, i keep coming back to Naxos & Antiparos, because you have a 7 year old, and There's just more there to keep her interested, at the beach in in the port towns, without either place being a "child-hive." All the above are independent-travel islands, not package havens, v. important for what you want.

Well this is late, and is not for the people who created this topic but I strong disagree with Greece not being able to base yourself.
I have done nothing but basing myself in Greece. Like literally every single time.
People tend to think that Greece is a vague fairytale island with pegasusses flying around, people drinking ouzo all day and having divine food. While the last 2 are correct, it's not like that.
- On every small and medium sized island you can base yourself and explore in every direction. Easy and simple.
- In Crete you can per-fect-ly base yourself. In Western Crete one bases himself in the gorgeous town of Chania and have every day a different drive and spectacular beauties to explors. From alpine and other worldly beauties, to the longest gorge in Europe, to superb beaches that rank in the top 10s of best beaches in the world. In Middle Creten you can base yourself in Rethymnon another gorgeous and smaller town in which every day you can have a different place and area to explore, from mountains, to lush forests, to barren and very wild south coast with roads in massive mountain cravises and so on. In Eastern Crete one could base himself in Agios Nikolaos a really nice town with again countless of things to explore from with the high lassithi plateau's, the 9000 year old history, the minoan civilization, the only natural palmforest in europe and in general 100+ gorges to explore and many other things. Way too much too sum up.
So we have had small and medium islands and Crete, which you can perfectly base yourself, and for smaller islands rent a quad, for medium islands and Crete rent a car.
Then the mainland. In the peloponnese you can indeed perfectly base yourself at Nafplio. From there you can do many many things. But who says just Naflpio. One could base himself for a couple of days in Monemvasia and explore Monembasia, the Taygetos Mountains, Sparta, Mystras, beaches, Elafonisos and the great simos beach, next to Eleonas monastery, Leonidio for climbing and so on. Then passing through the Taygetos mountains further on the west coast you can perfectly base yourself at Kalamata. A nice and vibrant city, with again every direction to do and see incredible things. On can visit the Mani Peninsula, the Diros caves one of the few river caves in the world where to navigate with a boat. To the Taygetos mountains from the other side, to great archaeological sites like Messene, or Basae. To castle towns like Koroni, Methoni, Pylos and at Pylos visit the lagoons and the Voidokilia beach with yet another castle on top. One can then base him/herself further North western part of Peloponnesos in either Patras or Chlemoutsi and so on and base yourself and visit the mountainous interior of Peloponnese, the mountain chains of Erymanthos, or Aroania or Kyllini and then the incredible lagoon and stone pine forests of Kalogria, or the wetlands of Symfalia, or the Diakofto train that goes through great mountain passages to Kalavryta. Or visiting archaeological sites like Olympia, and visit yet other great forests like Foloi or towns like Dimitsana, Stemnitsa. And there are many more gems, gorges, historic sites, mountain lakes etc.And that is the Peloponnese. Each of the 4 bases in the Peloponnese has so so many gems around that each base can last more than 2 weeks if one chooses to.
In Attika (Athens) one can do Athens in 3+ days if one wants to do and visit Athens more properly. Athens is absolutely an incredible city. But around it one can do beach days at the Athenian riviera, have great towns and villages, many great archaeological sites, then ofcourse the Temple of Poseidon ad Cape Sounio. The mountains around Athens deliver great hiking experiences. Then ofcourse Loutra with the natural hotsprings and welness. Ofcourse also the Argo-Saronic islands in front of Athens, like Spetses, Hydra, Poros, Aegina or some of the really closeby Cycladic islands. All are divine and different.
Then Thessaly. Thessaly has many gems. One could base himself Volos and go to countless places. From Pilion mountain and villages which is the place of the mythical Centaurs. to 9000 and 7000 years old archaeological sites of Sesklo and Dimini. to the Pindus mountain ranges that are very very long with endless climbing, hiking, walking and nature experiences. To Parnasos mountain chain, to Giona and Vardousia mountain chain all incredible. To Delphi and Arachova, many archaeological sites from classical period but also from Mycenean period much earlier. Ofcourse from Volos you could also visit the virgin forested Sporades islands where Mama Mia is captured. Or visit the island of Euboea, which is a 170 km+ long island which separately one could base him/herself. One could visit the plastira lakes and then Agrafa mountains. One could visit Meteora an other worldly place with incredible views. And so much more.
Then western Greece.
One could base himself at Lefkas, or Preveza or Arta and visit or explore the Ambracian gulf,
The incredible island of Lefkada with ultra blue seas, the Pindos mountains, the wetlands of Messolonghi, the many mountains and mountain lakes like Kremasta, the many archaeological sites like Nicopolis. visit the Acheloos river and valley with stunning alpine environment. Or ofcourse visit the many Ionian islands by boat. And again. So much more from these "base" places
Then Epirus. In Epirus one could base him/herself in Ioaninna and explore just like all these other base places the town. Which has many gems, and great architectures, castles etc. Also there are caves, tapestry of mountains and mountains that are covered with endless forests. One can visit Metsovo, or the Zachochoria: the 46 mountain stone villages. Or visit the Vikos gorge the deepest gorge in the world, or the many incredible mountains like Tzoumerka, Smolikas and Tymfi. On these mountains are next to climbing and hiking, great nature also dragon lakes, rafting options and the cleanest rivers of Europe like Voidomatis, Acheron and so on. Also special gems like God's bridge (Kalamas), or visit great archaeological sites like Dodoni, other great villages like Paramythia, or Parga at the sea which is gorgeous. Or visit a day trip to AntiPaxos island with superbly bluest waters. And so on. There is so much more here. Don't know where to start and finish.
Then Macedonia province. I based myself in Halkidiki many times. A great prefecture and part of Macedonia province. Halkidiki has 500 km of super soft sand beaches and great beaches. On the first finger great places and beaches, on the second finger truly incredible beaches like orange beach, Vourvouro and so on and great views from Mount Athos. The third finger is mount Athos and the only Monastic state in the world. Thessaloniki is a great city with many archaeological sites, medieval places, museums, and divine culinary food hotspot. Then you have many incredible archaeological sites like Olynthos, Vergina, Dion, Pella and so much more. The waterfalls and alpine town of Edessa. the Pozar hotsprings which is a great gem. The great lake of Kerkini which is one of the 2 most important birding places in Europe. To the mount Olympus which rises 3000 meters almost straight out of the sea is a great natural heaven, hiking and climbing place. I don't know how many times I have based myself here, but for many times 3 weeks where not enough.
Then Thrace. One can base himself in Kavala a great town, and visit the incredible island of Thassos which is famous for it's own historical sites, it's superb white marbles, dense forests and more. And with every island you could easily base yourself there separate from everything else. But that aside. Then one could go to the Nestos River delta, to the incredible Rhodope mountains which is a natural heaven of endless virgin forests overfilled with biodiversity. A heaven for nature lovers. To archaeological sites like Phillipi. to the Falakro mountain, Aggitis cave and so on.

OK, I hve a very busy week this week, but will reel off a few reactions to your list...
RE FERRIES -- May & JUne are the MOST changeable months for ferries, because the lines sometimes snatch a boat off the schedule for a week to retrofit for the busy high seasond.... and GTP gr does not list sailings this far in advance... you won't see a realistic schedule until at least March, etxcpt for the BLUE STAR lines which (bless them)are the very same almost all year round. What you CAN do, to find out the USUAL pattern of service, is to use the website http://www.openseas.gr and take advantage of its "Magic Calendar" trick! Put in your 2 ports -- let's say Santorini dp & Milos Dest. Then Click on Departure date & calendar comes up CLICK THE LEFT-H ARROW. You can roll it back to LAST MAY, 2018. Click on the DAY you want, NOT a DATE. example, you want 2nd Tuesday, that's May 15 2018 (in 2019, it will be May 14)/ Click -- and you'll see the Santo-Milo sailings for a whole week!! Brillliant!! this is not foolproof but gives u an idea of usual schedule.
RE ISLANDS --Of your list I would X off Sikinos ... it is little-visited, and there must be a reason... there's not much there to attract people. Same thing with Andros. Each of course has its advocates, but they are usually people who live somewhere like the UK, and who can "pop down to Greece" in 3 hours. That's not you nor me!!
For your List I would Substitute NAXOS for PAROS -- they are similar in size, IMHO Naxos beaches are better, bus network better, Port town more attractive, more scenic interior (mountains, village etc) better hikes etc etc. However, they are SO close, you could easily get a taste of PAROS. Right next to it is a small pllace I Loooove -- ANTIPAROS. It has a little 10-minute ferry, it's a FAB place to stay for 3 days... and if you stay there, you could go in to Paros & spend an enjoyable day, explore port town, maybe take a bus up to Naoussa (a prettied-up tourist place that pretends it's still a fishing village -- but the REAL fishermen are right along tthe waterfront in Parikia).
SEQUENCE PLANNING -- A map- http://www.explorecrete.com/crete-maps/images/greece.gif - (Click to enlarge) can help you think about a time-efficent route. Then tho you have 4 weeks, you may not want to spend all day on a ferry. You might start with a flight, and THEN ferry-hop along usual routes here's a VERY outdated route map http://www.greeceathensaegeaninfo.com/ferry-info-greece/greek-islands-ferry-chart.htm -- but it DOES show roughly the usual connections.
POSSIBLE SCENARIO (follow on Map) -- FLY to PAROS & 10 min Ferry to ANTIPAROS -- GREAT place to recuperate from long journey!!! ... 3 days (including1 daytime in Paros) -- Ferry (1 hr) from PAROS to NAXOS 5-6 days (THE most to do/see of all your list!! .. then Ferry (2 hrs) SANTORINI (3? nights there MAX) ... Ferry (1.5hr) to FOLEGANDROS (2 nights? mainly about high town of Chora, gorgeous!) ... ferry (1 hr( to MILOS (4 nights)... don't miss round-island sail! this island may require car rental ... Ferry (1 hr) to SIFNOS (4 nights?? it's Gorgeous... good bus system, stay in hills?) ... Ferry (1 hr) to SERIFOS --(2 days??) stay at Livadakia beach @ Coralli Bungalows ... your husband will LOVE this, only 2 places to stay on entire beach... only one "landmark" to visit -- the high town. That's about 22 days?? You can then go back to MAINLAND, and for an amazing CHANGE, take bus OR rent car & drive to NAFPLIO (the most beautiful Old Town in all of Greece)... stay 3-4 days. Your guidebooks will tell about it and here's a great website: http://www.visitnafplio.com -- it "feels" like an island because it's surrounded by water on 3 sides... but it's a great segue back into land, and only 2.5 hrs away from Athens, on a modern divided-lane highway. Final 4 Days: Athens.
That's enough to get started. Save Questions until you've researched the above, & worked out a sequence on a calendar with BOXES -- Here's an internet printable source - https://www.calendardate.com/printable_calendar/May_2019.pdf Put your location and possible to-do plans in each box -- and on "transfer days" allow most of day for that. This forces you to realize the time it takes to get around. Otherwise when people just make a list, they indulge in "magical thinking"... Instant transport, like the old Star Trek "beam me up Scotty" No can do.
And when you do come back, with the bare=bones of a trip outline, remember to recap basic information -- where u are from , ages, interests, time of year coming, # of days planned in greece ,,, because many readers will be meeting you for the first time, & the rest of us have failing memories he he! Good luck planning for your dream trip!

Buski, your last trip was 10 years and one baby ago.... and I think alas as a grownup you now will be happier if you plan ahead just a bit more. For example, have you noticed that with a child that age, you have a TON of stuff to lug along, and, annoyingly, the child will not help to carry ANY of it??!!! Not the back-carrier, nor the beach blanket, nor the fold-up "cane-style" stroller, nor the diaper-bag or lunch-bag ... None of it! Also you will find that when a 14-month old has had enough of the beach, and gets cranky and wants a nap in a crib, NOT on the sand... that baby will not be happy with walking back a half-mile uphill to the "bargain place" you were able to rent at the harbor. Don't Do It.
You're already tardy in finding low-ball prices in good locations ... but if you can get a PAROS room at Katerinas, grab it. It is right ON a beach.... OK, it's a mediocre beach but only a few yards from your room. That is KEY for you ... speaking as a mother who did holidays with children the age of yours.
As for ANTIPAROS, the best beach for you & toddler is directly SOUTH of the small port ... and I already did a quick check on Booking.com for you. I put in "dummy dates of Wed Sept 4 thru sun AM Sept 9 ... and the best place that popped up was ELENI'S ROOMS ... at €180 for 4 nights... it gets a guest rating of 8.8 ... it's in a street back from the harbor, with balcony pvt bath, electric kettle (good for heating babyfood -- put jar in bowl w. hot water). etc.
Another very modest-price place is MARIA"s PLACE, which is just about a 5 minute walk NORTH of the ferry pier. it is very close to a beach in that direction... along the curve of seafront of the village ... but not quite as nice a beach. I stayed in a Very nice place right on that curve (now called Sunday Hotel), and a place next door called Mike's Place is another favorite of Forum contributors... you'd have to decide, on basis of beach comparison & walking.

Paros, Ios and Mykonos are great options for party. Santorini is very romantic and Naxos has great beaches and is famous for its relaxed and family atmosphere. As for backpacking and camping style vacation, a lot of backpackers chose Amorgos, Antiparos, Anafi and Astypalaia. You will meet there a lot of young people who like relaxed and alternative vacations.