Linux

Fortunately for me, both my printer and scanner have worked flawlessly with Linux from day one (notwithstanding some CUPS shenanigans where it had problems finding USB printers, but that has nothing to do with the printer). Unfortunately for you, that means they are both fairly old already and probably not available as those specific models anymore.

My scanner is a Canon Canoscan LiDE 220. It's a fairly small model with a scan area just barely bigger than an A4 page. That suits me fine as someone who rarely actually scans stuff, as I can just stash it somewhere when I don't need it and pull it out when I do.

My printer is a Brother HL5340DL. It's about as big as you would expect for a personal laser printer (so not exactly handy anymore, but most people should be able to make it fit). It's ten years old now, cost somewhere around a hundred Euros when new, survived two moves and still works flawlessly, including the duplex function. When setting it up in CUPS, I found the generic PCL drivers to work much better than the Brother-specific ones. Just as a hint for others.

When looking for a scanner, check the SANE database: http://www.sane-project.org/sane-mfgs.html

Edit: I forgot something, my scanner does not work "flawlessly" after all: If I scan at low or medium resolutions, the scan results get messed up. It looks like the scanner software gets confused about how long exactly each scan line is supposed to be and puts the line breaks in the wrong places. That's probably a bug in sane-backends, but I have never followed up on that one, because my workaround is simple and works fine for me: Just scan at 1200 dpi and then downscale stuff. Still a bug though, and saying the scanner works flawlessly would be wrong.