Yikes. I'm generally a real fan of Malaysia and have been to all those places, but I'm not sure I'd recommend any except as jumping off points. I thought Penang was a bit disappointing but maybe you can make a go with a car rent or something. JB is horribly deprived of focal points by being bisected so much by roads and cars, KB is the conservative Muslim heartland (enforced boredom) and best as a transit point to the Perhentians, and I guess KK is least-worst though a bit drab because of being flattened in WWII. Kuching is much better and has some atmosphere and also a base for nearby national parks. With KK there's the TAR national park (islands, beaches) and maybe an overnight climbing Mt. Kinabalu, plus a few good places to eat. Sandakan was very drab but workable for the orangutan place and a trek to the lower Kinabatangan (one of the best short trips I've ever been on).

As far as just the city goes I've liked Kuching and Labuan the best, but if you factor in daytrip possibilities then some others become viable. You can also get good value for lodging dollars in the lower midrange.