Sandys place is really great - it's really close to the beach, remote and very quiet. Really cool to hang out and kick back. The balcony is huge, the rooms are nice, sleeping here while listening to the waves was very comfortable!
But please don't be like me and forget your drivers license because you won't be able to get around a lot, if you're not willing to hitchhike or walk for 2-3 hours, a car is absolutely necessary for Naxos :D