1] Please consult the LQ HCL here: http://www.linuxquestions.org/hcl/
I have always been happy with HP printers, but the Colour Laserjet 2600n was difficult to set up until I found some extra drivers.
The cheapest printers will be the most difficult to set up, in my experience.
You can always ask the manufacturers which of their printers is compatible with linux. You may not get an answer, and that may not mean the printer will not work with linux, but it is a bad sign.
It depends on how your "PXELinux boot server" is set up. I have never heard of "PXELinux"
Welcome to LQ!