I ditched my HP Deskjet a while back and replaced it with a cheap Samsung ML1710 Laser which just works great. It's pretty quick, quality is good, and it's small.

Replacement toners are about as much as the printer itself, but a quick google reveals that the toner can be easily refilled for about £8 - I've refilled it twice now and it's still churning out good quality prints. With "toner save" turned on, it seems to last almost for ever anyway.