Sorry if this is covered somewhere but I couldn't find it! I need recommendations on a good starter NAS

Build it yourself, avoid proprietary solutions. If you're after power efficiency go with some ARM board with PCI/M2 slot to use as SATA ports, if you want more performance and want to run a few services on it, get a second hand computer like an HP mini or even a full desktop.

I what would recommend is instead a Mini-PC like the HP EliteDesk 800 G2 DM or the Dell OptiPlex 3050 Micro.

If you plan to create a small NAS for storage and self-host a few services even an old laptop will do it, however there are advantages to picking a mini PC. Those machines are quiet, don't require much power and some can even fit a 2.5" hard drive so you won't need external hard drive enclosures.

Mini-PCs are also cheap second hand, you might be able to get an 8th Gen Intel CPU for 100-200€. Sometimes you'll find really old models (i3 CPU + 4 GB of RAM) selling for 50€ and while those aren't usable anymore as a Windows desktop they're are still more than enough to run your NAS/Cloud solution. I would pick something 6th gen or more recent.

For eg. for 100€ you can find an HP Mini with an i5 8th gen + 16GB of ram + 256GB NVME that obviously has a case, a LOT of I/O, PCIe (m2) comes with a power adapter and outperforms a RPi5 in all possible ways. Note that the RPi5 8GB of ram will cost you 80€ + case + power adapter + cable + bullshit adapter + SD card + whatever else money grab - the Pi isn't just a good option. Aside from the big brands like HP and Dell there are other alternatives such as the trendy MINISFORUM however their BIOS comes out of the factory with weird bugs and the hardware isn’t as reliable - missing ESD protection on USB in some models and whatnot.

A very important thing for you to consider is the storage / hard drive interface. On a Pi you're usually constrained to USB for your hard drives, however on a Mini PCs you've the following options:

• USB Storage - is slower and USB isn't very robust, not recommended, the only advantage here is that you don't have to DIY anything;
• Some of those machines come with a SATA port and space for a 2.5" hard drive, either use it a single drive if you don't need much storage or get a 5 SATA port card to expand it;
• Recent models come with a NVME M.2. slot (PCIe) and that can be turned into 6 SATA ports with a cheap adapter like this.

In both SATA cases you just have to throw NAS hard drives and a cheap power supply at it and you'll be done. SATA is faster and way more reliable than USB for storage, it won't randomly disconnect and you will be able to take full advantage of the disks, no speed limitations like in a typical USB connections. Personally I would pick model that has both the SATA connector and the NVME slot and then use the SATA connector for a small 2.5" SSD (boot drive) and the NVME with the adapter above for the NAS hard drives - this option will give you the best performance.

Software: run barebones Debian and install everything from scratch OR use something already made like TrueNAS Scale or OpenMediaVault.