Personally, I have a Brother HL-1440 printer that I've had no problems with at all. It's modestly priced (as far as lasers go: about US $200), but it's been a while since I bought it. I don't know if it's still in production.
Anyway, for other guidance, you can check
Linux Printing for information on what printers are compatible with Linux, and then start searching for retailers.