Quy Nhon in Vietnam - unspoiled, off the tourist trail, super friendly
Kuching, Malaysia (on Borneo) - and the entire Sarawak State - the only place in Malaysia that turned me on - also unspoiled and friendly, much wildlife
When you go to Laos, head straight for Luang Prabang and bypass Vientiane.