avoid the ml1600's or whatever the really cheap samsungs are they will be winprinters (gdi?)
look for something with postscript or hp pcl compatibility, laserjet iv and 5L's and certain brothers have served me well, hang on that sounds kinda wrong, brother is the make of printer!
look at linuxprinting as someone mentionned, and make sure there is a cups driver for it.