They had great music on the C64.
I used to compose on the Amiga using The Mod-Tracker format.
Although they used Samples, it was still quite small songpackages.

Midi also still stands. Its the perfect format for small
mobile games. If you have to keep under the 300kb limit.
..for the whole game...