If the printer is connected to the Linux box, or the network, HPLIP does a good job of handling both HP inkjet and laser printers. If you do get a Laser Printer, don't get a Samsung. I made that mistake. While the resolution was good and it printed on two sides of the paper automatically, it would smudge and used a propriety pcl, so you have to install their program to print. Another thing, don't assume that every Laser Printer is a postscript printer.
I think that one of the main advantages of a Laser Printer over an Ink Jet is that the printout won't smudge, and won't fade as fast. An inkjet would be much better for pictures however.
If you get an HP, check out the HCL at the HPLIP website: http://hplip.sourceforge.net/
Since it is a HP that you have hooked up to windows, another solution is to hook up that printer to the linux box instead and to ofter the printer share to the windows machine.
The problem you are having may be with the windows config. You might try enabling Unix Printer Services or access it through an IPP: protocol.
Another thing to try is to install hplip on your Linux box anyway, for the purpose of providing the additional drivers that it installs. ( Uninstall hpijs first, as a newer version may be supplied by hplip ). Check out the hplip website to see if the exact printer model is supported. If it is, even though printing to an smb printer share doesn't use hplip, it may work if the hplip package supplies a PPD file for your exact printer model.
The website has a chart, where the print class listed is "DJ3600".
Yet another option, if the printer is a usb printer is to get a jet direct device and put the printer on the network.