If you’re looking for a decent setup but maybe not the cheapest- Nvidia shield with an external hard drive would work very well.
You could always build or buy a nas and just run Plex as an app through either your current fire stick or get a cheap Roku stick (although now you’re back in the same ad garden for a player but Roku is minimally invasive imo- especially with a pi-hole for dns)