I can't really assist you with your PIC selection (though you've not really any specific h/w needs...eg PWM, USARTS etc ....so I'd imagine most of the PIC 18 range would suffice), but just wanted to chime in as another recent PIC novice/convert.

I'm using my PIC to control just one stepper motor - this stepper is used as a way of traversing enamelled wire onto a coil winding motor. Basically, the main DC motor has an encoder disk. The PIC counts the stripes from this disk & every x stripes (to work out how far it has travelled) it then sends out a pulse to the stepper.

I actually went the simple/lazy way & used a dedicated IC to hadle to stepper interfacing - a UCN5804.

You project sounds really interesting - good luck!