I would still recommend Lattice as a starting point. Both Diamond and Radiant run on Linux (running both currently).
One small and reasonably cheap board (not ultra cheap) is the Upduino 3.1 with a iCE40UP5K. I think this would be a nice learning tool. But it has a limited number of IOs and nothing on board to play with except the FPGA, power supplies, a flash chip and a RGB Led. The iCE40UP series is widely available for a few bucks.
Supported by Lattice Radiant.
To start with, MachXO2/MachXO3 boards would also be a decent option. Regarding dev boards, unfortunately, Lattice has drastically increased prices. Their MachXO2/3 "breakout boards" were around $25, now their price looks insane, but you can probably find third-party dev boards.
Supported by Lattice Diamond.
If you want to play with open-source toolchains, the iCE40 series (including iCE40UP) is supported by Yosys/Nextpnr too. The ECP5 as well. The MachXO2/3, not that I know of.
No experience with Efinix so can't comment on that.
But apart from the chinese FPGAs (such as Gowin), for low-cost you pretty much have Efinix and Lattice. Other vendors tend to have more expensive FPGAs and dev boards, but if your budget can get up to $100 or a bit above, you can also have a look at Digilent FPGA boards. For Xilinx (AMD) FPGAs, it looks like currently the cheapest option there would be this:
https://digilent.com/shop/cmod-a7-35t-breadboardable-artix-7-fpga-module/A Artix-7 will bring you significantly more "power" and max frequency than the Lattice iCE40UP or MachXO2/3, but for beginning, I don't think you'd really need that. Benefit of Digilent is that they have good products with good support.