Another vote for ThinkPads from me.
On my R51 the Slackware install was very smooth, and overall I am very happy with the machine's performance and features.
I got a model with Intel Extreme Graphics card and 3D acceleration was nice and easy to set up , not blistering performance but more than enough for what I use it for.
That said, XavierP gives good advice on what flavour of Linux will be the easiest to set up.
If you buy a machine that comes with XP pre-installed then why not set up a dual-boot situation until you are more comfortable with Linux? If you have to pay for XP you might as well have it there just in case things go wrong while you are still learning the Linux ins and outs