When travelling to East Malaysia (Sabah and Sarawak), what is the recommended starting town? and which town should be the final landing point? I will be flying from KL and going back to KL afterward.
The plan is to at least visits the famous towns.
Ok, Since I travel to Sabah a lot, here is my take on your plan.
Hope you make it to these stunning towns in Sabah Borneo! I have visited most of the places there and they are amazing in my opinion.
I have visited Borneo many times and its a beautiful destination. The major draws for me to Borneo are the jungle scenery and the native tribal cultures.
If you have a lot of time and want to experience all of Borneo, I would recommend flying into Kuching and out of Kota Kinabalu (or vice versa) with a stop in Brunei.
In Kuching, Bako National Park, the crocodile farm, and the longhouse tribal tours are pretty cool.
Bako National Park:
In Brunei, there is an incredible patch of virgin rainforest in Temburong National Park that has a nice jungle treetop walk.
In Kota Kinabalu, you can climb Mt. Kinabalu and visit the Sipadan Islands for nice diving/beaches.
You could take buses or fly between each city depending on how much time you have. Brunei is relatively expensive to fly to but there is a cheaper airport in Miri, Malaysia which is very close.
For Saba, Kota Kinabalu is a good starting point. It's a convenient small town with a good range of accommodations and easy access to the rest of Saba (plane, bus, vans, cabs). You will also be able to reserve tickets for Mount Kinabalu.
All in all, a good place to start your trip and get some nice food before diving in the wilderness.
Can't give any advice about Sarawak, though.