{type}_template is a filter inside the get_query_template function. That function is called by a series of functions called get_home_template, get_category_template and so on. It allows you to very specifically target templates.
You can see it in action in template-loader.php, where the $tag_templates variable is defined, binding conditions like is_home, is_category and so on to the functions. Depending on the condition the function is then executed on the line where it says $template = call_user_func( $template_getter );.
A bit further on in the file you see the template_include filter. This is the last possibility to change the template before it is actually loaded. This means anything you may have done with {type}_template can be overruled here.
So, if you have full control over your install, the semantically most correct way would be to use {type}_template, because that filter is meant to keep track of template changes under specific circumstances. It would keep your code more readable.
However, if you want to make sure plugins are not overruling your {type}_template filter, you would opt for template_include.