Any luck for sites on shared hosting?

It depends on what you want to achieve. This module (media_thumbnails) is just a plugin manager and does not have special requirements. There are however contributed modules to generate thumbnails from various file types. They might need special tools to do this. Here are some examples:

• media_thumbnails_pdf needs ImageMagick to generate a thumbnail from a PDF
• media_thumbnails_video needs ffmpeg to extract a thumbnail from a video file
• media_thumbnails_svg supports multiple tools, but the resulting quality might differ

What about shared hosting? Besides saving costs, the main reason to use it is not needing to manage the operating system yourself. It's not less capable by default, but it depends on the provider which features will be available. For example, there are shared hosters that support tools like ImageMagick, while others don't. It's the same for features like ssh access, Composer, OpCache or a memory limit high enough for Drupal - you can get them with shared hosting, but not every provider supports them.

The alternative might be using a managed server, because this offers more resources and usually a bit more flexibility in terms of installed tools, but of course at a higher cost.

Does this answer your question?

I am using media_thumbnails_video which like you said needs ffmpeg.

Per my check most (if not all) host companies will not offer ffmpeg on their shared plans because it is resource-intensive. A user attempting to install it will also need root level access on the server which a shared hosting plan will not offer.

I spoke with my host company now and they said,

... ffmpeg is not supported on any of our hosting plans due to security considerations and resource intensiveness.

So like I feared, there seems to be no luck for sites on shared servers.