I vouch for the Raspberry Pi Zero W. It comes with WiFi included which is cheaper than buying the non-wifi version + adding an own USB adapter, it works out of the box, raspbian is debian based, it’s reasonably cheap setting you back something like $15 (the zero without WiFi would be about $10).
It’s tiny and its power consumption is very low (measured by the oh so scientific method of touching the processor after it ran for a while and it’s quite cool).
And there is no recurring costs. Also it’s just cute. I think that last point really sells it 
Here, this is what it looks like:
There’s a guided text mode assistant which gets your wifi running in no time. It’s Linux easy mode. Also slow mode. But who cares.