I’d like to offer my custom post type as a Plugin, so that people can use it without touching their theme folder. But custom post type templates — such as single-movies.php — reside in the theme folder. Is there a way to get WP to check for a single-movies.php in the plugin’s folder? Hooking a function into the Filer Hierarchy? Or get_template_directory(); ?

You can use single_template
filter hook.
/* Filter the single_template with our custom function*/
add_filter('single_template', 'my_custom_template');
function my_custom_template($single) {
global $post;
/* Checks for single template by post type */
if ( $post->post_type == 'POST TYPE NAME' ) {
if ( file_exists( PLUGIN_PATH . '/Custom_File.php' ) ) {
return PLUGIN_PATH . '/Custom_File.php';
}
}
return $single;
}