You might have a hard time finding a new printer in stores that is compatible with 10.4. So, try your luck with the on-line sales sites, for example www.staples.com and search for "refurbished" printers. You can find some of the older models that will be supported in 10.4 if you look at the detailed system requirements.
like this one, for example:
http://www.staples.com/Brother-Refurbished-EHL-4150cdn-Color-Laser-Printer/produ ct_470644#desc_content
Try other local stores that are also on-line sellers, they may have a free-ship-to-store option, if you have a local store that is convenient also. I found a refurbished Brother MFC-8660DN a few years ago that is supported under OS 9 from Staples on-line.
Another way to see if a particular model is supported under a particular OS, is look on the Support/Download section for HP, EPSON, Brother, Lexmark, etc, for OS drivers and see which driver versions are available for each Mac OS version.