Can a module install a theme? I would like to know if it is possible to make a module install a separate theme as well. Should I just ask that whoever installs my module also downloads that theme to have a better experience?
Yes, it is possible. You can create a MY_MODULE.install file, add a HOOK_update() where you can call theme_enable and variable_set() to set it as the default theme.

Here is an example:

/**
 * Enable my_new_theme and set as default.
 */
function MY_MODULE_update_7001() {
  $themes_to_enable = ['my_new_theme'];
  theme_enable($themes_to_enable);

  // Set the theme as default.
  variable_set('theme_default', 'my_new_theme');
}