Technically the best thing to do is to write a plugin that will also provide the template(you can of course allow the theme a way of overriding that - for instance by using locate_template( 'my-plugin-template.php' )
to check if the template exists in the current theme).
You should then process the form submission in your plugin - I would either check for the form values on the template_redirect
action filter for instance(you can do it earlier as well - like on init
for instance), or even right before loading the template if you don't need to do a redirect.
The idea behind using a plugin, vs putting all of the code in the theme is that if you decide to change your theme in the future, it would be more easy to keep the same functionality in the new theme as well.
I personally try to avoid calling plugin files directly(the third option you thought of) - not that it has any side-effects that I know of, but it's just my own preference.