It’s a huge island though, so be sure to plan ahead if you go.
Must be a different Tioman I have been to!? Anyhow, Tioman is nice if you want to relax, it’s really quiet, beautiful beaches and you can go snorkling or diving at reasonable rates. Have been told the islands further north are even nicer (Pulau Redang) - hard to imagine.
You can take a plane from KL (around 45 minutes I think) and touch down on a small strip considered an airport.
Anyway, KL is a good start and beside myriads of shopping centers you could go down to Merdeka square and try to climb the tallest flag pole in the world (yes, they not only have the tallest building but also the tallest flag pole).
Around there are a couple of nice old buildings, the court and the railway station in particular. As well look out for the two rivers merging with the mosque sitting inbetween - the place which gave KL it’s name. Just near Merdeka Square. There is also a butterfly and deer park near it (further west) though I haven’t been there.
China town is an interesting place if you want to shop, ahem, Rolex watches, branded T-Shirts and VCDs. All genuine of course.
Places to hang out: Beach Club area (near Hard Rock Cafe).
Actually KL hasn’t much in terms of sightseeing, so it would be good to go further away:
West of KL, directly at the coast, you find a small town called Kuala Selangor. Near to it (a bit closer to KL) you find a small “kampung” (township) where you can take a boat and see millions of fire flies at night, sitting in the bushes along the river bank.
Visit Kuala Selangor in the afternoon - forget the nature park but go up the hill instead and feed the monkeys - and on the way back see the “kelip-kelip”. Around 8pm is a good time I rekon.
If you miss Chinese culture too much go up to Genting Highlands, the one and only casino in Malaysia; also got a theme park. It’s a small city on top of the mountain (gotta see it to believe it), refreshing cool and a great view if the weather allows it. If you plan on staying during a weekend make sure to make a reservation, else the Singaporeans which come with hundreds of buses will take up all the place. Use the cable car (longest in Asia) instead of the crazy taxis to get up the last bit.
If you don’t like noisy Genting maybe Bukit Tinggi is something for you, same highway as leading to Genting but a few more exits down the road - again a resort on a hill but more (nature) to see. Here the French town of Colmar was recreated, the ground floors house restaurants while the upper floors serve as hotel rooms. Simple and not cheap but nice, gives you a bit of European flair. Sit ourside on the terrace in the morning and sip a coffee - nice.
The place is also known as Colmare Tropicale. Visit the Japanese garden or the Botanical Garden from where you can trek into the jungle. Supposingly there is a view point from which you can see Genting, due to bad weather I couldn’t go last time. Got a golf course and paint ball shooting range there as well.
Expect possible construction sites around there, too, the plans for expansion and development of the entire area are HUGE (theme park, Spanish village, hotels, condos etc). Not sure if they have started though.
Melakka was mentioned and is a worthy day trip, around 1.5 hours drive south of KL. You can walk along the small shops in the center and go up the hill to the fort (or church?) from where you have a nice view on Melakka and the ocean.
Langkawi: ok if you are there the first time, though the beaches are nowhere as nice as the ones along the east coast. But you can easily spend a weekend there.
Penang: called the Pearl of the Orient but I strongly disagree, Langkawi is definetely nicer and Penang has not much to offer, small strip of beach with a couple luxury hotels along it is pretty much it. Been there many times on business but couldn’t recommend it unless you want an island with easy access (there is a bridge and ferry service which links it to the mainland).