Linux

Hardware wise, you'll be hard pressed to find any even half-way popular computer that can't run some form of Linux. So I'd say just get something that's within your budget. Those x86 APU-based mini pcs that you can find for ~$200 are becoming pretty popular for projects these days. Something like a Raspberry Pi or Orange Pi or whatever might also be fine depending on what you want to do with it, just keep your power expectations in check. If you want to spend more money on something with graphics hardware, I'd recommend going for AMD over NVidia, just because the drivers are built into the kernel and essentially no-hassle.

When it comes to software, especially if you're on x86, just arbitrarily pick one of the reasonably popular distros like Ubuntu, Fedora, PopOS, or any of the other ones you've probably heard of. One of the first things to learn about "Linux" is that there's a whole ecosystem of software projects behind it, and there is a lot of overlap between the software that each distro runs. Yes, there are some meaningful differences between, for example, Ubuntu and Fedora, but I think they are much less meaningful to a noobie (who is just learning the basics of Linux) or an expert (who probably knows enough to bend and customize just about any distro into whatever they want).

Small caveat #1: If you prefer to have a desktop that more closely resembles Windows (like the one of the Steam Deck's desktop mode) you might want to pick a distro spin that uses the KDE Plasma desktop. On the other hand, if you want to play around with something that's a bit different than what you're used to, it might be worth checking out a distro spin that uses the Gnome desktop. I can recommend them both for different reasons, so you might want to check out some videos of them to see what you're more into before picking. (Other desktops are available, these are just the two big ones! So there truly are a ton of options to explore here if you want to.)

Small caveat #2: At this point in time are you more interested in stability or customization? If you want a truly rock-solid Linux system that's hard to ever break, you might want to consider one of the new "atomic" distributions like Fedora Silverblue/Kinoite (or others), though you might find some of their limitations annoying. On the other side of the spectrum, if deep customization and flexibility is what you're looking for, then you might want to venture into the deep end with things like NixOS or ArchLinux, just keep in mind that they can be very technical and overwhelming for noobs. Personally I have been using Fedora Silverblue for a couple years now and I love the stability of it, and I can work around it's limitations with distrobox.

Another thing to consider is just using what you already have. For example, playing around with Linux in a virtual machine, setting up a Linux-based server on one of the popular VPS services, or just plugging your Steam Deck into a dock with a keyboard and monitor attached and playing with something like distrobox (which you can probably find a guide on how to set that up for your deck).