Good idea to buy a color laser, though, imho. My next printer will probably be a color laser. I really would like a scanner so that was part of the reason I was looking for an inkjet (multifunction).
I suggest looking for a Samsung, Brother or Lexmark (maybe even in that order?). A common model in those brands might offer the best chance at finding cheap ink/toner and I'd look for an online vendor who will ship to your area (as cheap as possible). Most of those have some Linux support but probably enough to run in native Linux.
When I get around to it, I want to get one and a genuine scanner (only scans) which I'll use in Windows or VirtualBox (don't see why it wouldn't work in that setting). The Samsung CLP-325 is around $100 but if you need better models, most in those brands are probably $200+.