Dell XPS M1330 preloaded with Ubuntu. No hassles of installation at least. In any case whatever notebook you choose, do a bit of research to find out that the wireless card works properly under linux. I have had decent experience with Intel's wifi cards since drivers are open source and hence included in most distros. Wifi is the number one annoyance on most notebooks.

edit : I wud advice to look for "Centrino" branded stuff. That usually works out of the box. But YMMV.