I can't really recommend a particular one but what you want to look for is something that does PCL print language not LIDIL (Lightweight Imaging Device Interface Language).
HP Deskjet 6122 seems to be one of many that fit the bill. We have a HP995C here that works fine. Most any printer that does PCL or PCL emulation should work fine. It looks like this all-in-one should work too:
HP PSC 2410 Photosmart All-in-One
If you see two printers with nearly the same features and one costs a fair amount more if you check you will almost always find that the cheap one is a winprinter.
I suggest you check the specs from the HP page for a printers that you might be interested in. The thing you are looking for is the PRINTER LANGUAGES, STD. It should be PCL with a version number, like PCL3. Get one, try it and return it if you don't like it.
The bottom line is that the printer should be supported if you attached it directly to the unix machine. What ICE does is provide a transparent path for output that that unix app would normally print to the unix printer to your windows printer instead.