L'idéal aurait sans doute été Sabah ou Sarawak sur l'île de Bornéo. Mais il vous faut prendre un avion et donc pas trop top.
Comme vous n'avez pas précisé de confort, je présume que ce n'est pas le principal.
Un programme Malaisie pourrait être pas mal est de commencer par Pulau Tioman (pulau veut dire île). Puis de faire un tour à Malacca avant de rentrer sur Singapour pour faire quand même une petitie visite de Sg.
Ne sachant pas si vous voulez faire le plongé, je fais comme si c'était oui, et donc je mets Pulau Tioman d'entrée de façon à terminer par du tourisme surface pour ne pas avoir de souci pour l'avion à prendre pour la suite de votre voyage.
De Singapore, vous pouvez prendre directement un bus pour Mersing (R&R Mersing Terminal).
Il y a deux compagnies qui font ça. l'un part de Newton Circus (Kaiho Coaches Tel: 07 241 8208, je ne connais pas leur horaires mais je crois qu'ils n'ont qu'un seul départ à 6h30 le matin) et l'autre du coin de Lavender street et de Kalland Bahru (Transnasional Coach Services 65 - 6294 7034, avec des départs à 9h 10 h et 22h). Cela vous oblige à passer une première nuit à Singapore. Les prix des bus sont de 20$S et 27$S respectivement selon la compagnie.
Sinon, vous prenez un taxi de l'aéroport de Singapour et vous allez au Larkin Bus Terminal à Johor Bahru (en Malaisie). De ce bus terminal, vous devez pouvoir trouver un bus qui part pour Mersing sur la côte est de la péninsule malaisienne (vous trouverez assez facilement sur une carte) et de Mersing, prendre un bateau pour l'île de Tioman. En speedboat (Auto Mersing 07 799 6019/3123 ou Blue water express 07 799 5696) vous en aurez pour une heure et demi et 70 RM par personne (4.2RM= 1 euro en ce moment, je crois). Le Seagull express (slow ferry) met 3h30 et coûte 50RM/personne (pécision : je ne garantis pas que les prix n'aient pas changé. mais c'est l'ordre de grandeur).
Suivant comme vous avez pu goupiller vos horaires, il vous faidra peut-être passer une nuit à Mersing, car si c'est le premier jour, vous n'allez pas tenir le coup tard le soir.
Sur Tioman, il y a plein de petits hôtels, centres de plongée etc... je vous laisse chercher sur google.
Pour revenir, vous reprenez le bateau pour Mersing, et de là (R&R terminal), vous pouvez prendre un bus pour Melaka sur la côte ouest. Pour savoir quand part le bus, renseignez vous à l'aller.
A Melaka, je vous recommande mon hôtel préféré : l'hôtel Puri qui est dans la plus pure tradition de la ville de Melaka, La ville historique de la Malaisie.
http://hotelpuri.com/
En face (et un peu à droite) il y a l'hôtel baba, un peu moins bien, mais pas mal non plus.
Il vous reste à revenir de Melaka à Singapour en bus, soit directement par Transnasional ou Delima Ekspres ou Metrobus Ekspres et passer un ou deux jours à Sg.
Je vous recommande une soirée au Night Safari à Singapore.