How to make my plugin theme-independent?

Shortcode is definitely a good start. It is very flexible in terms of where you output the content (widget, post, page, inside php function, etc).

You can also override the template output easily by using action hooks and custom post type that you create:

add_action('the_content', 'add_project_content');

function add_project_content($content) {
    // Only override the content of project custom post type page
    if (is_singular('project')) {
        // You can re-use original content stored in $content and simply add things before and after, or you can simply override them with something new
        $content = "whatever you want";
        $content .= somefunction_output();
    };

    return $content;
}

This will lift you up from having to deal with template files and worry about matching changes for theme updates. With these methods I get away with creating any extra template files in my child theme folder.