Help w/Greek Island Itinerary; Naxos vs Paros

• How long to stay at each location?

Discovering an island, even partially, takes at least 4 full days, and Naxos and Paros are the 2 largest Cyclades islands. So in a single week it would be useless and unproductive to go to more than one other island than Santorini.

Santorini is a special case since it is a mass tourism destination where thousands, even tens of thousands of visitors arrive every day and only stay a few hours (cruise passengers) or 2 days, 3 days max, and all cram into the same famous places on the island (Fira, Oia, Red Beach, etc.) to take a few pictures.

• We will be traveling to islands from Athens and then need to return to Athens for our flight home. Is it best to take a flight to islands
  or is ferry okay? Or ferry one way and flight one way?

• For travel logistics is it better to stay at one or the other first?

It's up to you. The main thing is to be back in Athens at least the day before your flight home.
The ferry trip between Santorini and Naxos or Paros in one direction or the other takes between 1h30 and 2h30 depending on the type of ferry, fast catamaran or conventional ferry.

Apart from the trip between two islands, you can fly on all your other trips.
Whether by flight or ferry, any trip will take you a large part of the day door to door, it means 3 days of travel/transfer logistics to visit Santorini and another island.

• Any recommendations for vegetarian/vegan restaurants on the islands?

Greek food offers a plethora of meat/fish-free dishes.

Hummus, tzaziki, melitzanosalata, fried cheese, cheese / spinach / green herb pies, dolmades, beans, tomatoes or bell peppers stuffed with rice & herbs, zucchini fritters. And is one of the healthiest in the world especially with the use of olive oil. So no need to worry about that.

• Any beach hotel recommendations?

I can't recommend any, I know the Greek islands quite well and I have my own opinion on where to stay but I never stay in hotels that I find too restrictive for my way of traveling.
Other forum members will give you some good tips.

Naxos and Paros both make good companion islands to pair with Santorini, you really cannot go wrong with either one of them.
I do have a suggestion though, fly to whichever island you choose and then take an excursion boat for a day trip to visit Santorini. Any travel agent in either island will have excursion tickets on Naxos Star or Alexander.

This means you don't have to sacrifice time making the island hop (checking in and out of hotels and waiting for the ferry ). Since you have so little time you probably should fly to your chosen island and return by air as well.
If it were me I would choose Naxos.

I have only been to Naxos and liked it very much but people who visit Paris like it as well. So not much help there.

I did want to say that I personally would not do the day trip to Santorini option. That gets you there when all the cruise ships are there. I would fly to Santorini and then ferry to Naxos or Paris and then fly back. We had some rough sailing between Santorini and Naxos and I was very glad I had bought airline tickets for our return.

If you only have a week for the islands then I would do 3 nights on Santorini, and 4 on Naxos or Paros. You also will need a night back in Athens the night before your international flight. It may be possible to find a ticket which flies from Santorini back from US. My brother in law did this from Washington DC through Munich. But if you have unconnected tickets, I would spend last night near airport.

If you can buy a ticket that has Santorini on same ticket as international flight, then I would start with Naxos.

We did this several years ago and found the easiest/fastest way is to fly from Athens to Naxos, take the ferry to Santorini, then fly back to Athens. The ferry makes the circular route and the ferry from Naxos to Santorini only took a few hours.

We've been to Naxos twice and loved it! Once we stayed three nights at the Galaxy Hotel (about 10 minute walk to the main town) and the other time we stayed five night's at Spiros Hotel (right in the town). Naxos is large enough to feel not crowded, has plenty of restaurants, and great beaches. We haven't been to Paros but understand it's very pretty, too. From reading, I think there will be more to see and do on Naxos, but not so much that it feels frenetic and overwhelming.

We stayed two and a half days on Santorini: the first day was the ferry there, then the bus ride to the hotel. The second day we wandered around and walked down to the Ammoudi Bay, and the third day we had a private guide tour us around the whole island and drop us off at the airport for our evening flight back to Athens. On Santorini, we stayed at Nikos Villas near Oai, right on the walking path about 8 minutes from downtown Oai. Santorini really is beautiful at night, after the cruisers leave. On the way back, we stayed at the Athens Sofitel airport hotel (right across the street) for an early flight back to the U.S.

It's important you plan the flow of travel because the ferries only go in a certain direction. I can't speak to any dietary restrictions.

Have fun!

Thanks to everyone for your suggestions. This is all very helpful information.

Well you didn’t ask but I’d take a day from Santorini and stick it anywhere else lol

We love Naxos and Paros , but for first timers would give the nod to Naxos .

I’d fly to Santorini - then ferry to Naxos then Athens and I’d make sure last night before international flight was in mainland .