USA west or east? check in any case AirMalaysia. From east USA also KLM might have good fare in February to Kuala Lumpur (last March I paied 515Eur return ticket from Europe to KL).
From West a good route could be going also to Singapore.
From KUL to Tawau or SIN to KotaKinabalu->Tawau fares are relative cheap.
If you have your international flight with AirMalaysia you'd better do a full ticket with KUL tawau leg included. it might cost less if you do an open jaw on return between Tawau and kotakinabalu, i did it once (open jaw means you arrive to somewhere and back from somewhere else). A stop over at KL on way back it would be good also for shopping

with airaisa you have the limit of 15kilos, with airmalaysia, if you stop at KL, you could also do the check-in at Sentral Station, where there is the fast train to KLIA.
if you had time you could split your holiday and do some days also at layang layang and feb might be pretty good for meeting hammerhead sharks
google for avillionlayanglayang dot com
btw when I took that open jaw flight ticket, then I bought a one way ticket from Tawau to KK and it was very cheap!