My ex was malay and subsequently lived on off in msia, just outside of KL. Roti pisang is lovely, but also make sure you try sambal undang and indonesian deng deng if you can find it!! NAsi goreng too!! I miss all those foods :-(
Regarding the diving, i have dived perhentian islands, redang, tioman and in borneo of course sipidan/mabul. If you can spare the time, get a flight from KL domestic airport to Kota kinabalu and in KK there are some dive operators (eg borneo divers) and you can arrange accomm/diving for sipidan and staying on mabul (which has fab macro life). If not then any of the east coast islands are nice. Tioman is my fave and have stayed at both the berjaya hotel and a small resort in salang bay. Tioman is a beautiful island and you can explore with some jungle trekking (though care lots of snakes!). Snorkelling in selang bay is nice and have seen turtles, bump headed parrot fish and lots nice fishlife. You can get a bus from the main bus terminal in KL (just ask operators) and takes approx 5hrs to mersing where you get the boat.
Pulau redang also v nice, amazing beaches, diving good also and you can snorkel with baby black tip reef sharks as there is a little nursey near the jetty point. The berjaya resort there is lovely and has an excellent beach. Highly recommended.
Perhentians nice and quiet, crystal clear waters and lovely beaches too, diving not bad, turtles and white tip reef sharks a highlight. Think we flew up towards kelantan to get to the departure point for those islands.
But if you can get to sipidan thats where the magic is. big stuff, small stuff, fantastic diving.