The easiest & most sensible way I can think of, if you want the theme and plugin to be as independent as possible, is to copy the custom page template files from your plugin’s directory to the current theme directory when the plugin is activated, and delete them when the plugin is deactivated, using register_activation_hook() and register_deactivation_hook().
That way you wouldn’t have to mess with the template dropdown in the page editor, and you wouldn’t have to hook into template_redirect.