KL is good if you like a modern asian city and you want to spend some time in bars and malls. I personally find it a little dull but there's always something to see just wandering, and as I'm sure you know already that's often an experience in itself in Asia. Culturally speaking the National Museum and the Islamic Art Gallery are worth a stop over, as is the National Mosque and the Lake Gardens. Batu Caves is just out of town and is a must see for me, just incredible but can be really overloaded with tourists. Chinatown is fantastic, as with any genuine Chinese quarter. Sunway Lagoon used to be a pretty epic water park too, apparently it's been upgraded but I haven't been since I was a kid. Obviously there's the Twin Towers if you're that way inclined. There are heaps of ethnic quarters as well that are worth a look...Ampang Jaya for Korean, Bukit Bintang has a sizeable Arabic community, loads of Indian and sub continental areas too, Burmese, everything you can think of really.
Melaka is a great old town that used to be the cente of the Dutch shipping trade, so it's full of history. And some great food. It's a quiet little town though so not a lot to do after dark. Heaps of museums and historical sights. Jonkers Street is the best place for food and has a good night market.
Penang is the best spot I reckon. Easily the best food in Malaysia. Batu Ferrenghi has some great beaches and markets. You can hop the Ferry over to Butterworth just for a poke around for an afternoon, there are some great food stalls and markets over there (especially the wet market-which are morning food markets) and despite being where the RAAF base is it's much less frequented by westerners. Georgetown has all the history from the colonial times (parts of it are UNESCO listed) and fantastic food, you can poke around the fort, check out the Khoo Khongsi which is an old gang house. Also Kapitan Keling Mosque. Kek Lok Si (AKA Temple of a Thousand Steps
) is a great spot and a beautiful temple with a cool little market stretched all the way up the massively long staircase to the temple at the top. You can go up Penang Hill, either by train or hiking through some pretty cool jungle, to get stunning views of the island. The tropical fruit farm is actually really cool. Snake Temple, War Museum, if you're there during Chinese New Year it has hands down the best celebrations and does every festival with style. There's hundreds of markets, great food everywhere, you can have a wander around the Weld, which is the jetty community where the oldest Chinese families still live. It's as multicultural a city as you'll ever see.
From Penang you can get a 2-3 hour ferry to Langkawi, which is a pretty top island. It may not always have the most stunning beaches depending on ocean currents at the time but it's a great tropical stop over to just chill out for a few days, hang with other backpackers and drink in a resort on a budget compared to loads of other places.
If you're really keen on the natural side of things you can head over to Sabah/Sarawak for some of the best diving in the world IMO...also orang utan sanctuaries where you can spend the day interacting with orangs, elephant and sea turtle sanctuaries, rainforest trekking, Mt Kinabalu (although it's a 2-3 day trek, it's pretty amazing). There are also national parks on the mainland where you can see Elephants and Tigers, but you have to be incredibly lucky for the most part.
Pulau Tioman off the east coast is one of my favourite island destinations. Nice resorts, some excellent diving, and if you really want a powerful experience you can dive the wrecks of the HMS Repulse and Prince of Wales, WW2 Battleships.
Kuala Terrenganu is an interesting little place to spend a few days. More local than a lot of the bigger tourist destinations if you want to get a bit more of an authentic Malay experience. It's also the beach where WW2 started in the pacific.
The Cameron Highlands are a good place to stop over for a little while. There's not a whole lot up there bar tea and strawberries and rainforest but it's a nice spot to escape the heat and relax given the average temp is in the low 20s.
Johor is the city on the very southern tip of the mainland, easy access to Singapore for the day or a few nights and some of the best seafood outside Penang, with a pretty good spread of markets and other cultural attractions.
