Must I have a Visa at all?
I yes, can I get a Visa on arrival (at the airport if arriving by plane, or at the border if arriving by bus/train) ?
As a French citizen, one does not need a visa to stay in Malaysia up to 3 months (90 days I suppose, the exact number of days is not specified on the website for some reason).
See the website of the Malaysian embassy in Paris for further details.
See also the Wikipedia list of Visa requirements per country for French citizens - although you should always triple check what is mentioned here with what official authorities say.