Ubuntu + HP Omnibook XE3 + Orinoco
I run Ubuntu on a HP laptop recently bought on eBay.
The model is a Omnibook XE3. It has a Celeron 750 Mhz CPU and 192 Mb of RAM, a 10 Gb hard drive and a TFT 13" screen.
Installation of Ubuntu on this machine went pretty well, not a single issue during the installation. The whole hardware has been detected and installed without any glitch.
For wifi connectivity, I bought -from eBay as well- an Orinoco silver card, automatically detected as using the orinoco firmware. That's probably the best card you can get if you want a very good reception.
My access point is a Linksys WAP54G bought on LDLC.be, probably the best piece of hardware you can get (at least version 2) as an AP.