[bubblegum57]

As for running out of storage I meant the library metadata stored on the Fire TV Stick.. And as long as you can ssh into CE it shouldn't be a problem to install whatever you want there, even if it's not a Kodi addon. So currently I'm wondering what the best solution would be.. Also for my first question, would the ODROID be powerful enough to run some services besides Kodi?

NAS with VM running services - Fire TV with Kodi App and Netflix -> probably most expensive and traffic intense but most convenient
Android TV device dual booting with CE-Kodi and Android TV-Netflix - Storage directly attached via USB Hub -> feels hacky and could break apart easily I guess
ODROID N2+ running services and Kodi - Fire TV for Netflix -> is it powerful enough?
Custom HTPC running services and Kodi - Fire TV for Netflix -> expensive and would need intensive research on hardware, so not really preferred

You can add an external usb stick to gain extra storage for the fire stick. Troypoint is a thing to google, but it comes with a lot of other crap trying to get you to buy a vpn. You need an OTG cable & usb stick.
I don't know if the Odroid would be powerful enough, you could ask at the CE forum. although it is the most powerful amlogic device at this time. 

Android TV device dual booting with CE-Kodi and Android TV-Netflix,  these android devices do not include single board computers like the Odroid or N2 they don't have android. EG X96 Max + the android from these devices won't run 4K netflix as they are not certified.

Hmm, and the affordable NASes come with 1GB RAM only. Additionally the VM would need access to the USB port for the tvheadend tv card, and I don't know if thats even possible.. Seems like custom is still the way to go

a nas with 1GB ram is at the bottom end of the market, VM's are only on the higher end. also, to run a tvh server from a nas, you need a compatible usb tuner, there are not many. HD homerun would probably be ok. BUT you need to check that there is a TVH server package for the particular nas. 

I am not a fan of Single board computers, by the time you have added remote, or dongle, case psu etc. 

I am running a X96 Max +. I have installed CE to sd card. It uses a S905X3 this does have temp issues, although I don't. 

With CE you can run a TVH server & client, using a usb tv tuner, or HD homerun (not cheap)

The X96 max is relatively cheap, I am not recommending it. 

A box with S922X is better but more expensive.