You are really asking two questions: "How do I make the internal search work better?" and "How do I change the search form to give it more advanced functionality?"
To change the behavior of the search I would say Relevanssi is the best plugin if you are trying to improve the "native" WordPress search behavior. The free version does pretty much everything you ask while the paid versions do that and a lot more.
The alternative to using Relevanssi to fix the WordPress search is to dump it altogether in favor of Google Custom Search for WordPress. Assuming you are using an SEO plugin to create a sitemap (and if not, you should be!) then you can control the category and tag archives for all post types and give priorities. An added benefit of switching to Google is that it can also spider any PDFs you may have whereas Relevanssi cannot.
Either of the above will give you more flexibility and control over searches on your site and may solve the issue.
However, if you want to change the behavior of the search and combine that with an advanced form then my recommendation would be to look at Pippin's Advanced Search Shortcode plugin as it allows you to generate both an advanced form with inclusion/exclusion parameters and modifies the search to support that. Not a free plugin but also not very expensive and Pippin does quality work.
I tend to prefer a simple keyword search over having to puzzle through a form with multiple checkboxes, drop downs, etc. The more I have to fiddle with a form to find something that should be 5-10 keystrokes and a click, the more likely I am to try another site.