In iOS 9 there are no categories listed in settings>general>spotlight search. Just Siri suggestions toggle and a toggle for each app.
But I fixed the issue. Restarting the iPhone or the iPad was not enough. I had to hard reset each of them and now I can see apps and Top Hits. Previously Top Hits were just not there.
Thanks for the help in confirming that it should work like I expected!