I've always have been a fan of HP laser. You can get something similar to the HP Laserjet 1020 for about $150. You can also use 3rd party toner to save money. I usualy get my HP 1012's toner 3rd party for about $25 vs HP's $70.
My previous printer was an HP Laserjet 4L which lasted me 10 years or so. I have been running my HP Laserjet 1012 for about 3 and a half years so far and it's been a nice little work horse with no problems. I would expect that the 1020 is just as good. HP also has a few other models out there. Some cheaper, some more expensive.
I would be very surprised if Linus and solaris didn't have a propper driver for them and if they didn't you could still use the generic PCL drivers.
Of course, there are other brands like samsung, Dell and Brother but I have never used any of those but there are those that like them.
I don't know if there are any near you at the moment, but CompUSA is still in the process of selling off it's inventory. I was at my local store tonight and saw that they were selling Samsung laser printers for $82. Frankly, that's less expensive than most first party toner cartridges alone.