The HP Color LaserJet is a discontinued model but an incredible workhorse (you can find them used -- especially on ebay -- and they're almost all still great printers). I use this for text documents and anything the kids want to print as the cost per copy is significantly lower.
Then I got a Canon PIXMA MP-500 all-in-one (copier, printer, scanner and photo printer -- the only thing missing is fax capabilities, which I still don't understand why they left that out). I use this primarily as a photo printer and the output is incredible -- pretty much photo lab quality! I picked this up at BestBuy after comparing output of several printers (including Epson and HP).
A key selling point for me was that the Canon uses five cartridges, while most HP and Epson and other manufacturers tend to use two (black and a combined color cartridge). The problem, at least to me, is that with one color cartridge once you use up one color, the cartridge is basically done and you have to replace it, even though there is still ink for other cartridges in the tank. This Canon uses Black, Photo Black, Cyan, Magenta and Yellow. So when the Yellow runs out, you only replace the Yellow cartridge. Much more efficient and saves you money. Some newer Canon photo printers come with six or eight cartridges, which should make them even better (although I compared the MP-500 to a six color Canon and preferred the output of the MP-500).
I used to have a Canon MultiPass (all-in-one with fax) F80. The cartridges for that one are almost identical to the MP-500's. And the old unit worked very well with compatible cartridges, which can be picked up online rather inexpensively ($3-$5 per cartridge). The MP-500 will have compatibles available this summer, which will provide wonderful savings as well.
As for paper, I have used Staples high gloss photo supreme as well as Kodak glossy photo paper and both seem to work equally. But I haven't had the printer long enough to know if fading will become a problem with either paper. And a friend of mine did a flyer with color photos printed on 28# copy paper done on the HP laser and the output there was amazing as well!