It’s quite a common misunderstanding of the word “Malay”, but no biggie. In Malaysia, “Malay” specifically refers to the ethnic group. I think you meant to ask about Malaysian food instead, which comprises Malay, Chinese, Indian, various other ethnicities, and even combinations of ethnicities.

If you do specifically want Malay food, I think nasi lemak is a must try.

Then again, different states have different niches. The state I’m from is famous for Peranakan (Chinese+Malay) food, and I would highly recommend that.