Ah-ha! Success!
I wanted to uninstall Search Application and and Solr Search Application and reinstall them but there were too many dependencies. I then found the “compute changes” button for both applications -
There were a number of changes, so I reset them all and my search started working.
Edit: After some more digging, I’m not proud to say I created the database with latin encoding - might have something to do with why everything got a little screwed up… Converted the DB, all good now.