とりあえず世界遺産は漏らさずに

順路ではバリ島のタマンアユン寺院、バトゥール湖畔のウルン・ダヌ・バトゥール寺院、ジャティルイの棚田ほか２ヶ所、ボロブドール、ブランバナン、マレーシアのマラッカ、ペナン島(ジョージタウン)、アユタヤ、スコータイ、ルアンパバン、ハロン湾、フエ、ホイアン、アンコール

他にもありますが最低これらは行かれたほうがいいかと。全部で２週間程度ですから。これに移動時間とバンコク、チェンマイ、行かれたい島々を足すだけですから５０日もあれば十分でしょう。
ジャワもブロモ山、ソロ、バンドンなどを入れると１日の移動が少なく楽です。

超絶景では東南アジア最高峰で世界遺産のキナバル山と世界有数の美しい湖、スマトラのトバ湖が外れますが、トバ湖はジャカルタ、空路メダン、空路KLで可能です。