Io sono stato sia a Lanzarote che a Fuerteventura.
Io non scarterei a priori Fuerteventura, è vero che è ventosa, ma è un'isola bellissima soprattutto per chi vuol fare nudismo/naturismo e, visto che ci vuoi andare d'estate, il vento non è un grosso problema.
Se poi stai nella costa Est o sud-est, lì è più riparato dal vento e ci sono posti davvero paradisiaci, fra tutti la spiaggia di Sotavento.
Anch'io avevo scartato Gran Canaria e Tenerife per gli stessi motivi: troppo affollamento.
Lanzarote più che il naturismo è da visitare per lo spettacolo della zona dei vulcani. E' veramente suggestivo, merita veramente. Charco del Palo è veramente carino, è una località dove non solo stai nudo nelle calettte, ma puoi girare nudo tranquillamewnte anche per il paesotto. E' vero, comunque non c'è spiaggia.
Vale la pena visitare anche punta Papagayo, al sud dell'isola, ci sono cale veramete belle, anche se più affollate.
Ho visto Graciosa dall'alto, da un punto panoramico su una montagna a Nord di Lanzarote e sì, è un'isoletta tranquilla e ..... deserta. Ma veramente deserta, piatta e totalemte brulla. Sinceramente non mi ha attirato molto, ho come l'impressione che dopo un po' mi sarei 'annoiato'.
Ma magari è proprio quello che cerchi tu.
Un saluto.