Sounds like you may have installed an add-on/extension that has hijacked your new tab page in order to get you to use their search tool.

Here is some information on troubleshooting add-ons: https://support.mozilla.org/en-US/kb/troubleshoot-extensions-themes-to-fix-problems

If you're unable to find out which add-on is causing the problem, or if none of them are the culprit, then I recommend downloading Malwarebytes free software and running a malware scan.

Malwarebytes: https://www.malwarebytes.com/

Let us know what you find out.

Do a malware check with several malware scanning programs on the Windows computer.

• https://support.mozilla.org/en-US/kb/troubleshoot-firefox-issues-caused-malware

Please scan with all programs because each program detects different malware. All these programs have free versions.

Make sure you update each program to get the latest version of their databases before doing a scan.

• Malwarebytes' Anti-Malware:
  http://www.malwarebytes.org/mbam.php
• AdwCleaner:
  http://www.bleepingcomputer.com/download/adwcleaner/
  http://www.softpedia.com/get/Antivirus/Removal-Tools/AdwCleaner.shtml
• SuperAntispyware:
  http://www.superantispyware.com/
• Microsoft Safety Scanner:
  http://www.microsoft.com/security/scanner/en-us/default.aspx
• Windows Defender:
  http://windows.microsoft.com/en-us/windows/using-defender
• Spybot Search & Destroy:
  http://www.safer-networking.org/en/index.html
• Kasperky Free Security Scan:
  http://www.kaspersky.com/security-scan

You can also do a check for a rootkit infection with TDSSKiller.

• Anti-rootkit utility TDSSKiller:
  http://support.kaspersky.com/5350?el=88446

See also:

• "Spyware on Windows": http://kb.mozillazine.org/Popups_not_blocked

EASY FIX (for me):

Click the Firefox menu button (3 horizontal lines at right end of toolbar). Click Add-ons (icon that looks like a jigsaw puzzle piece). When the Add-ons Manager tab opens, click Extensions (on left). Click on the MyWay extension. Click the disable button. Fixed!

I had this problem on a brand new laptop. Like you, I uninstalled and re-installed Firefox but the problem remained. Then I used the Mozilla Support link in Pkshadow's reply to another posting on this topic and started the troubleshooting process -- this was the step that fixed it.