Hi Lew -- and everyone. A great conversation here.
(Sorry, and I've mentioned this before, you can all start your own conversations here even if you're on Digest because when you use that nobody knows what the Subject is any more and fewer people see the new message. And so much for Vietnam getting C-130's too.)
Now, Lew, it's not clear just how young/old, budget/splurge -- and especially how adventurous your cousin and his wife are for a two-three weeks off-the-beaten track visit to all three countries of the former French Indochina. I'm useless on Cambodia & Laos these days, but can't tell you how many times I've given travel advice and the recipients ended up doing their own thing out of Saigon's Pham Ngu Lao tourist district. (My biggest disappointment was a good Aussie friend's son whom I'd arranged to meet up with our similar age grand-niece in Saigon to go local -- and then he met a bunch of uni friends from back home and that was that.) Can your cousin ride a motorbike or does he need transportation?
Anyway, just overall, it's never been easier to get around Vietnam these days -- and I don't mean on that on-and-off backpacker bus or that damned train people keep gushing about. There are very good public bus companies now, most notably orange-coloured Phuong Trang Futa, whose clientele are mostly all Vietnamese but can get you wherever you want to go at a reasonable price. Everywhere you go in Vietnam, you'll find someone who speaks -- or trying to speak -- English and help you out in the usual way. It's a great way to meet the locals too.
Another is using Grab, Vietnam's Uber equivalent and out of Malaysia/Singapore to get around by car and motorbike (as passenger). You don't need a credit card and just sign up using a local number. (You can get SIMs right at the airport but might wait until you get into town and your hotel.) Grab is good around cities and you can even use them for trips out of town like, say, up to the Cu Chi Tunnels, My Tho or wherever. (Just get a quote!) Another is Xanh SM from Vietnam's electric vehicle manufacturer, Vinfast, who use cars & motorbikes.
The best suggestion on travel, other than flying domestic up to Danang/Hue and Hanoi (presuming they start in HCM City) is to use a bus to get to a destination and then explore around there by local transport, including hiring a motorbike and explore on your own, or sign up with a local tour operator. (Helps the local economies too.)
For off-the-beaten track tours: Often overlooked by foreign tourists, I'd suggest the two-hour high-speed ferry from Saigon down to Vung Tau, the old Cap St Jacques of course, and spending a couple nights at a beachfront hotel or preferably something in still-somnolent Back Beach area. The town is full of resident & visiting Aussies whose troops were stationed there & up north at Nui Dat during the war and you can avoid them or not. But there is a good mix of western and Vietnamese food there. From there head up the little visited batch of beaches north Long Hai all the way to Phan Thiet and then Mui Ne to its east. (One thing you'll find everywhere is that Vietnamese are now great travellers and it's not unusual to see hardly any other westerners around.)
Alternately, get a Phuong Trang bus from HCM to Phan Thiet, about three hour east, and book into a resort at Mui Ne. Remnants of the last of the Cham Kingdoms give the region a unique feel, plus it's almost desert-like at the junction of the SW Monsoon and NE winds. Great sand dunes & all that. The Russians were pretty thick on the ground a few years ago and chased other foreigners away (Nha Trang too until even they escaped invading Chinese tourists) but they're not there any more. Great accommodation. Nice local villages. Lots of seafood.
Oh, another off-the-beaten track would be to fly to Con Dao (formerly prison island of Con Son with its famous Tiger Cages) and still quite pristine and southeast of Saigon in the East Sea (don't ever call it South China Sea there.) Accommodation is not too flash, thank goodness, and I can put you in touch with a tour guide friend who lives there. From there, get a ferry to the Mekong Delta's Soc Trang province with its heavily Southern Cambodian (Khmer Krom) population, most visibly in its temples. And then a bus up to Can Tho (nice riverside resort there now) and another bus back to HCM City. (Chau Doc up the Hau, or Bassac River, on the Cambodian border is another great destination and not that touristy.)
Further north, I'd give Nha Trang one big miss -- and Da Nang too -- which has now drawn in a huge influx of US retirees on the cheap and changed their entire character with beachfront high rises. Plus that damned VinCom resort on Bamboo Island really sucks.
In fact, I don't even like Hue all that much, especially the arrogant locals (even the cyclo drivers) and the way they've over-done the restorations of the old royal palaces. If you cousin is interested in history & stuff, why not get up to Dong Ha or even Dong Hoi just north of the Ben Hai River and old DMZ between North & South and base there for two or three days. Do a tour up Route 9 to Khe Sanh and Lao border on the southern side, a very moving cemetery too, and on the northern side the Vinh Moc Tunnels and especially inland to 'Ha Long Bay on the land' of limestone karsts with the Phong Nha Caves and that only recently discovered cave that's hard to get into unless you're signed up & spend lots of money. But truly overlooked region of Vietnam.
Now, further north, I would recommend Ninh Binh which has some really nice spots, more of the karst landscape and nice little B&B's to stay. Some touristy boat trips (OK) but nice wild goat feasting and don't forget the truly overlooked Phat Diem Cathedral complex down near the coast. (Read Graham Greene first.) Get a bus from Ha Noi.
Also around Ha Noi, I'd suggest a bus up to Ha Giang and then get a local tour, or hire a motorbike is you can do that, up into what's truly the most spectacularly beautiful part of Vietnam. Stay two or three days. Give Sa Pa a miss. Another alternative is Cao Bang and then trips up along the Chinese border northeast to the Ban Gioc Waterfall or Pac Bo to the n.w. with its foundational history where HMC returned from exile to begin his revolution against the French. Both lovely areas.
I have mixed feelings about Ha Long Bay but it is worthwhile doing in a proper way which I haven't quite figured out. (The overnight cruises are OK but the generators are going all night and you wake up to a bay full of other such boats. So no real feeling of privacy and on your own.) Further up the coast, however, you can get your own impressions of the bay with some tours operating there. Another great destination, always a favourite, is Hai Phong, northern Vietnam's main port. A pleasant train trip (which should still run and a taste not the full-belly of the run from Saigon) and a city full of French colonial architecture the Americans couldn't bomb because there were British and neutral country ships in the harbour. From there, you've got a backdoor entry into Ha Long with Cat Ba Island which has some good accomodation and a great way to head north up into the bay on a day trip.
On weather. Your autumn will be rough & humid in the North but getting nice & cooler in the South at the end of the Rainy Season. OK in the Central.
Finally, Lew, it'd be good get some more basics on where your cousin & wife are coming from budget-wise -- and I guess their age too -- to fine-tune things. But these are my overall suggestions and I do hope they are interested. They are most welcome to get directly in touch.