> You can provide a small Makefile that the user will have to invoke in
> order to compile the C source.

The user doesn't even have to invoke it: package-install can invoke it
(indirectly) by having something akin to

    (eval-when-compile (shell-command "make"))

in one of the Elisp files.