My only lasers have been color since the beginning of the year, but before that, I had an HP6MP, which still stands as my favorite. It was relatively inexpensive (I think the 2100 (?) which replaced it goes for under $800), quick, and clean. Stingy with toner, I could make a cartridge last for almost a year (I'm a home-based page layout/writing business).
When I switched up to color lasers (trying to print 15 color photo covers *each* for five separate clients in one morning cannot be done on a color inkjet), I got an HP4500, and was frankly a little disappointed. It was marginally quick, but my older 6MP was much quicker (even in terms of black-ink only prints, not counting color mixed or full color prints). Color prints were fast if you sacrificed quality. It's all a trade-off of course, and all things considered, I'd probably recommend the 4500 if your color needs only entailed basic color insertions (lines, text, small photos, etc.).
The real champ has been my Tektronix 850DP. This printer kicks ass over everything I've ever used. It's amazingly fast, even in photo/1200dpi mode. In standard mode, it spits pages out almost as fast as a higher-speed copier. The real lagniappe is that black ink -- or black colorstix, this series of printer uses solid ink, not liquid ink or toner -- is free for the life of the printer. You just call up Xerox, pay a nominal shipping fee ($10) and they'll send you thousands of the black colorstix if you have the room to store them (I even had trouble convincing the woman on the phone I only needed 150).
RALPH