Isn’t a search box (that uses your default search engine) displayed there by default when the New Tab page is set to show your Top Sites? See the image in the New Tab page in Firefox article. Or is this not what you want?

No, for some reason it isn't being displayed.

I've looked at these articles, and they show the search bar at the top but there's nothing about what to do if it disappears. They're great about setting tiles, but don't mention the search. I DO have google set as my default search. Any further suggestions?

Would you happen to use any add-on, non-default theme or a userstyle script working with one that causes it, a user.js file in your profile folder, or a userContent.css file in its chrome subfolder?

If unknown or not found (or frankly first) I would try to see if the box displays in Safe Mode to see if an add-on is responsible. If these steps do not help, have a look at this and this question.

If all this doesn’t fix it quickly, you could also choose to perform a Firefox Refresh. This can be done by opening Help > Troubleshooting Information (or from the dialog when starting Firefox holding down the Shift key when starting Firefox), but it would require to reinstall any add-ons.

I did a refresh a couple of days ago. I'm not doing it again. And no, I don't have a user.js file in my profile folder.

It does show properly when I run in Safe mode. Good grief. Now I guess I have to figure out which extension is going this.

Okay, it looks as though it was the Classic Theme Restorer addin. The good news is that when I disabled it, most of my selected changes were there anyway, which is nice, except that I like my tabs below the bookmarks toolbar, but I think there's an option for that.

Well done. There have been more reports of Classic Theme Restorer causing "glitches". Unfortunately it will no longer be supported as of Firefox 57 due to the WebExtensions transition as you may know so there is not much hope of current issues getting fixed, also looking at its development version status. You could of course try to contact the author or visit its support page/forum at mozillaZine.

For the tabs below the bookmarks, there is no option or preference for it but you can use a userChrome.css file if there is no other add-on that can do this. The Tabs On Bottom add-on is one, but also seems to stop functioning in 57 for the same reason.

This question shows content for a userChrome.css file that should still work, even in 57 (tested). This question which is more recent shows different code for it that will also create a different appearance for the order of the bars.

As for the New Tab page: in 56, the Search box can be enabled/disabled separately from the tiles.

Would you consider your question(s) solved?