We're cruising out of Singapore in Jan 2027 and are thinking about spending about a week (+/- a few days) in Malaysia before working our way down to Singapore for a few days before jumping on the ship. While we've been to Singapore a few times, we have not been to Malaysia yet. Our main interests are food, street/night markets, and interesting neighbourhoods.

I have penciled in KL, Penang, and possibly Malacca as locations to visit based on our interests, limited time and to a lesser degree climate for that time of year. Are my choices logical?

I'm also having a tough time wrapping my head around the best logistics getting to Malaysia, routing these three cities, and then making it down to Singapore. Ie. Trying not to go too hard since we'll be jetlagged, trying not to double back, etc. Any suggestions would be great.
Initial thoughts are to trying to get a reward flight from YVR (or elsewhere along the westcoast) to somewhere in Asia and then hop over to KL or Penang. I suspect there would be more options flying into KL but flying to Penang initially would prevent us needing to head north to Penang and back down again.

Any thoughts on whether to fly, take a train, or take a bus between KL, Penang, Malacca, and Singapore? We're willing to spend a few more dollars on convenience but with these "relatively" short distances, I'm not sure how much more convenient flying would be with all the associated timesinks associated with flying.

TIA

Sort of know peninsular Malaysia all too well. One thing is that food can be very regional if not local hence the expression commonly used in east Asia, "This place is famous for its...." "Place" can be anything from a particular establishment (which will have imitators) to a whole town.

Air travel between the major destinations would be the most reliable if train is not an option (may be difficult to book ETS - the long-haul train service - if not booked in advance of major peak demand). Takes about an hour between PEN and SIN and KUL is circling around (last flight into KUL, the a/c flew south of MKZ before turning around to get in line with the incoming KUL traffic). In KL, you have the option of SBZ (the former KUL) which has much lighter traffic than the current KUL so may be less prone to ATC delays and reduced flight times. Flying into Singapore, you also have the option of XSP though SIN isn't a major hassle to get in and out of despite its volume and size.

Other than the booking hassle above, long-distance trains are limited by seat availability and frequency (not enough train sets/extra carriages).

I would say that Penang has probably the most to see of historical interest. I would be tempted to give the place at least 3 nights, staying in or on the edge of Georgetown (E&O may be quite affordable if booked in advance, and there are quite a few charming Chinese mansions). PEN was once difficult to get to by air (had to go via KUL or SIN but more options now. Not sure what 1-stop connections there are from (presumably) YVR. CX via HKG should be one (and I guess SQ via SIN another).

You can get to/from KL by rail (have to get over to the mainland rail station at Butterworth) or air (KUL which is quite a way south of KL city, or perhaps SBZ which is a little closer), as well as car. The latter would give you opportunity, if you have time, for Cameron Highlands (I find only the south part, up to ~Tanah Rata) interesting these days. Some people like Ipoh but I am not sure of the attraction. There is also Taiping.

KL is a big sprawly place which just doesn't have that much charm (and this is my impression since the mid '70s). Almost pressed to say what is of historical interest (other than some old colonial mansion neighbourhoods which were recently used as standins for colonial Singapore. It seems the Petronas towers are the big tourism draw. The administrative capital of Putra Jaya (close to KLIA but a pain to get to/from due to incomplete highways) may be worth having a look as to what a futuristic Islamic city looks like (it was/may still be more surreal visually if there's a haze in the air as it gives it more of the feeling of an artist impression).

Malacca/Melaka I'd give a whole day (so possibly 2 nts). Jonker St, the Dutch fort/church, ancient Chinese cemetery and the river walk are the highlights. It is pretty much reachable by road only, so either bus or private car (self-drive or chauffeured). MKZ lost all scheduled service for a while but it does appear TR has resumed limited service on weekend (F, Sa, Su) to SIN. Interesting enough, and I would give it at least a whole day (so 2 nts). The rail line is quite a ways inland so not a viable option. IIRC, Jonker Street comes alive for the weekend but it's also noisey and congested with foot and vehicular traffic (got to enjoy that in November).

Since middle of last month, you can now take the train between KL and Johor Bahru (not sure how one gets from JB to SIN other than by bus as the metro line isn't operational yet) which may be a good option if you think air takes too much time and road may be hindered by traffic (see below).

I have avoided mentioning bus but they are available. There are the luxury ones with 3 abreast recliner seat configuration as well as the more standard 4 abreast configuration. Reputedly/reportedly some bus lines are betters/safer than others (I've only taken the bus between KL and KUL). The only drawback with bus into Singapore is having to disembark (with bags?) at both side of the causeway border for passport control. The main highway/expressway in Malaysia (so Butterworth/Penang to/through/around KL and to Johor Bahru/Singapore can be occasionally closed due to traffic accidents or come to a crawl because of roadworks. Road traffic volume in Malaysia has been increasing due to promotion of the local car industry and you have the mixed bag of speeders and very slow commercial truck traffic for roadways that are only 2-3 lanes er direction with the predictable results.

In summary, if you do fly into KUL, I would continue by air to PEN. From there, 1st choice is air PEN to KUL followed by train. If trying to fit in Melaka, road. Melaka to SIN, air if the schedule fits, and if skipping Melaka, air KL to Singapore.

Hey thanks for the detailed response. Very much appreciated!

Our plans have slightly changed due to new limitations on when we can depart YVR (missus' project commitments). Originally, we were hoping to have more time pre-cruise. Instead, now we're planning to head back to Malaysia after we end our cruise in HK so we have a little more flexibility in terms of a visit of Malaysia even though that means kind of doubling back a bit.

The timing suggested for Penang and Malacca seems to align with what we're thinking as well as a short visit to KL. The info about travel between cities/towns was helpful. With the additional time we now have, we might be more inclined to try to make some quick visits/side trips to towns in between our main stops.

Also, not sure now if we'll fly home from SIN or KUL now depending on what flight options/fares we find.

Unfortunately there are not too many places to visit in peninsular Malaysia that are that interesting. I've been too many times and have, frankly, run out of places to visit (and it didn't take very long). East coast is better for getting out to the islands if you are interested in diving and snorkelling. There are some interesting drives through the rain forests (particularly one places where Malaysian aboriginals were selling the ripest and freshly-picked jack fruit (there's a national park but that would involve hiking with all the usual stuff such as insects and leeches). Mostly, it seems to revolve around the food, and that takes some research.

I have also just learned a trick about buying shorter distance tickets for the long-distance (ETS) trains in advance: Try adding stops further up or down if KTMB isn't offering tickets as "short" distance (e.g., Ipoh-Butterworth) tickets are not sold more than 24 hrs in advance.

You could also consider ride share for the shorter haul road trips. Grab (good for taxis too) is the pre-eminent one followed by Tune (Air Asia) and Maxim though the latter appears to be primarily in east Malaysia.

We will be visiting Singapore then Malaysia in March. Fly to SIN, 5 nights. Will book a flight from SIN to PEN. Many direct every day. Will finalize arrangements for a driver through our Cameron Highlands hotel. Then get a driver to KL, from which we will depart. Not terribly expense... similar to Thailand pricing, for lodging and transport. Would look into the train but would have to book a ride to/from Ipoh to get to the highlands anyway, so will just take the drive all the way. All looks in order. Hope your itinerary works out also.