Drupal - How do I override a default view template from another module?

Your feature should implement hook_theme_registry_alter(). The use case you describe is exactly what that hook is for. The example code linked on the API page should get you started. The basic idea is to target the entry that corresponds to the entry that views_theme() is inserting into the registry, and change the template to match the one in your feature.