IBM used to have good Linux support and compatibilites. I used to test various distros on my T41 including Debian/Gentoo/Slackware/Arch and SuSE. Sorry, haven't tried any RH/FC based distros on it.
IBM can also fulfils all of your requirements, except price.
Second choice: Samsung
Dell should NOT be considered because not all models can work fine with Linux.