Well, the intellectual challenge part I can understand, but I think you'll quickly run into the limitations. A microprocessor simply doesn't have what it takes to do the trajectory planning etc. that is required of any capable CNC machine. As for running linux, it was a no-brainer for me. I popped the live CD in, did the install, ran EMC's configuration wizard and was running within an hour. As for the extra hardware the only thing required besides the stepper drivers was a breakout board for the parallel port.
Again, I'm not dissing the whole idea of CNC on the arduino, just pointing out the deficiencies. I am in fact working on a single axis arduino controller for a digital positioning system, the reason I dove into this microcontroller business. I'll post it here when it's done.
Good luck on your endevours! I'll be watching to see what you come up with. 