Bali as Phuket and West coast Malaysia will be in the midst of the monsoon and often the beaches there are red flagged. Split up your time between Ubud and a beach destination there and you'll have a fantastic anniversary.

Conngrats

As late in the fall as you can go

weather2travel.com Climate Guides

Bali/Villa Batujimbar is located in the heart of Sanur, on the southeastern tip of Bali. This four suite ...

www.perfectplaces.com/vacation-rentals/108098.htm?feedid=330

would be great for 5 days would not hop around...

More rain risk but Phuket JW Marriott bidding Priceline my #2

Happy Planning!

www.wannasurf.com/spot/Asia/Indonesia/Bali/sanur_grand_hyatt

Hyatt also good for surf there very good...

Ubud inland no beach komaneka.com Monkey Forest my fav there

Very pretty if time permits.

I agree, for that time of the year, Bali will have the best weather.

Thanks all. We're pretty flexible actually with the times of year we travel so weather issues aside which of these locations do you love the most? And then which times of year is best for that locale? Someone also just suggested Sabah in Borneo and we can take a non-stop flight from Perth to Kota Kinabula so I'm intrigued. Thanks.

Sabah is an amazing destination. Of course, you don't go to Sabah just for beaches (though they are beautiful), but you go for the opportunity to see the orangutans. But with a mere 5 days, you wouldn't have enough time for a beach and a jungle stay.

With 5 days, you want to go one place and stay... that could be Phuket or Bali or a location in Malaysia. One suggestion I have is to go to Penang and stay at the E&O in Georgetown. It's not a beach location, though you are on the water, but Penang is both fun and fascinating. (you can stay at a beach location on Penang, but the beaches aren't that nice)

Langkawi has never seemed as interesting to me as the other places - there have been some trip reports here. Read the reports and see if it still sounds intersting to you.

My husband & I celebrated our 25th anniversay in Bali 4 years ago and we loved it. Would go back in a heart beat. Have fun planning-Chris

Hello ardie514:
The first step, if you travel Asia, is to have a look at the rainfall averages for your travel month. The east coast of Peninsular Malaysia is still OK for September and October.
We “discovered” Tioman Island this year: great beaches and a broad variety of accommodation. Find details at http://wikitravel.org/en/Pulau_Tioman. There are direct flights from Kuala Lumpur or exec busses from Kuala Lumpur to Mersing with speed ferry connections.
Have a look at our travel diary:
http://konniandmatt.blogspot.com/2011/07/17-jul-19-jul-2011-mersing.html,
http://konniandmatt.blogspot.com/2011/08/19-jul-22-jul-2011-tioman.html.
Happy travels, Matt.

We returned from our fourth trip to Bali this past Sept. I must admit we were very disappointed with the over-crowing. If you want beach and surfing though the waves are for beginners to low intermediates then Sanur is quite nibe but to rtry to have a guide take you sightseeing is no longer any fun. The only thing about it that it thatg is attractive is the cost, $55-$65 for 10 hours.
If you are at all interested in snorkling there is some great spots in the Redang Islands. You can fly there from the city airport of KL in 45 minutes. The beaches were quite nice but not luxury. I would suggest going between late March and August to avoid the heavy rain periods. April-June wojuld be ideal. Also, if you did go I would spend 2 days in KL with one day devoted to the city including the petrones Tower (get there at 8 AM and you will get up early if not a weekend day for some magnificant views. You might want to go to a 2-3 of the major malls, they are huge and with great variety. You could also fit in a vist rto the Batu Caves in that one day. On a second day you might want to travel to the awesome Cameron Highlands by car servive. It is breathtaking seeing the roling hills of tea plantations as well as the gypies that live in the area. It is a long and a bit costly, 6 hours RT, but well worth it or stay overnight at one of the lovely lodges in the tea plantation area. Then go one to the Redang Islands for 5 days. They are very near the Prehentians but the difference is to go to the Prehentians you travel 8-10 hours by bus and ferry vs. a 45 minute flight. If you want to say you have been do as we did which was harter a boat and in under 1 hour we were in the Prfehentians but I can tell you thr snolrkeling or diving wa no different. But he boat rental for the day was $350 and that was 5 years ago. We were not impressed with Phuket's beaches on our vists in 2000 and 2007. We went to the Redang Islands in mid-March and the weather was great all 6 days.

Hello StanKase:
Yeah, a short detour to the Cameron Highlands seems to be a lovely idea, nicely complementing a beach holiday at either Pulau Redang or Pulau Tioman (btw, both have airports and there are regular flights from Kuala Lumpur to both islands).
Ardie 514, just have a quick look at our travel notes (with many photos) about the Cameron Highlands:
http://konniandmatt.blogspot.com/2009/02/cameron-highlands-03-feb-06-feb-2009.html
You might even spot one of the rafflesia flowers, the largest flower on earth!
Happy travels, Matt.
www.konniandmatt.blogspot.com