Congrats and welcome to the club of Windowsless computers. ;D
I'm thinking of picking up a cheapo Toshiba Tecra P II 350 MHz laptop myself and run Linux on it.
I've used Tecra (at my former company as desktop) and they were great. I heard IBM Thinkpads are great for Linux too. :-\