Not a particular model recommendation for your situation Susan, but I have an HP 2710 All in One that works very well under both XP and Linux (I don't have Vista). HPLIP (a driver package HP helps to develop for Linux) has all functions but faxing from the PC working. I think the fax from PC function is me not having something set up correctly, but the faxing from the printer works so not a big deal.
Mint setup the printer automatically, scanning even work without any intervention from me. Well, once I installed Xsane scanning worked.
So my recommendation would be to narrow your search around HP models.
Hope this helps some.
All progress requires change, but not all change is progress.
--Henry Steele Commager
...there are some...who use change to promote their careers. And then there are those...who use their careers to promote change.