Choosing one depends on you case.
If you wish to make a restriction in your app to search only for restaurants then I would use Category Search.
If your app allows to type place name or address then the Fuzzy search is a better option.
Points of Interest Search is something like a Fuzzy search witch idxSet=POI.
With Nearby Search you get a list of all POIs near the specified location and you can’t filter them.
And the last question - Structured geocode just requires to put particular address parts in specific fields.
So in my case of wanting to look for restaurants in a city, I should use Nearby Search, right? (The only thing the user types in is the city name, they don’t type in the word “restaurants”.)
I would use Geocode to get lat/lon of a city and then use them with Nearby search.
If you need this list to be strict (only restaurants from this city) then you could consider using Geometry Search.