My wife and I love Singapore and I'd like to introduce her to some more of SE Asia. The easiest way to do that is to start in Singapore and play the history card to go through places like Malacca and Angkor Wat, but I can't find any tours that run through that route - all either fly directly to Siem Riep or via Bangkok. Are there tours that meet that description?
Most of the regional airlines offer fly / stay packages, not exactly a "tour" but the basic logistics are covered. Then you can book daytrips to see the ruins through the front desk.
There are local package tours, but they tend to be geared towards local clientele, so may or may not be suitable for you comfort style or language. Plus the bus trip from Malaysia through Thailand to Cambodia is fairly long.