These are the two beach destinations most Vietnam itineraries end up choosing between, and they are not similar places. One is an island resort destination; the other is a city with a beach. Their wet seasons also fall at different times of year, which settles the question more often than any preference does.
Start with the month
This is the part people work out last and should work out first.
Phu Quoc's dry season is roughly November to April. Nha Trang's is roughly January to August. Four periods follow from that. November and December: Phu Quoc is dry and Nha Trang is at its wettest, so Phu Quoc. May to August: Nha Trang is dry and Phu Quoc is in its wet season, so Nha Trang. January to April: both are dry, and that is the only stretch when the question is genuinely about preference. September and October: both are wet, and neither is reliable.
Picking the wrong one for the month is how people end up on a grey beach wondering what the fuss was.
Opposite coasts, opposite seasons: Phu Quoc · Nha Trang. (Enable JavaScript for the interactive map.)
The character difference
Phu Quoc is an island with resorts strung along its coast and a small town in the middle. You stay at a property, you use its beach, and you take taxis to anything else. It is a holiday destination in the conventional sense, with the developed south and the quieter north offering genuinely different experiences.
Nha Trang is a city. The beach is public and runs along the front of it, there is street life behind, and you can walk to dinner. It is cheaper, busier, less polished and more Vietnamese in daily texture, with a large package-tourism layer on top.
Getting there
Phu Quoc is a flight. There is no sensible overland route — the ferries from the delta are slow and only make sense if you are already there. That means a dedicated leg of the itinerary, and an airport transfer at both ends.
Nha Trang is on the north-south railway and the main highway, so it drops into an overland route without a detour. If you are working your way down the country, it is on the way and Phu Quoc is not.
The visa point
Phu Quoc has one feature nowhere else in Vietnam does: the visa requirement has one exception for tourists, and it is a stay of 30 days or less on the island of Phu Quoc, arriving and leaving directly without clearing immigration on the mainland. That condition is the catch. It only helps if the island is the whole trip, which is not most people's Vietnam itinerary — but it does make Phu Quoc possible as a standalone holiday without a visa application, which nowhere else in the country is.
The beaches themselves
Phu Quoc's are better. The sand is whiter, the water is clearer in season, and Sao Beach in particular is the kind of beach people photograph. The trade is that the good ones are spread around the island and you travel to them.
Nha Trang's single long municipal beach is clean and perfectly pleasant, with a city behind it rather than palms. It is a good beach; it is not a beautiful one.