I'm just getting started with PIC's as well, so I'm not too familiar with all the different ones. Just find a page, you probably can find one at microchip, that has all the features of a variety of microcontrollers listed together. The biggest concerns are probably program space and I/O pins, and you can figure out what you need for those after you get some programming knowledge and design the rest of your circuit.
I'm very book-oriented, so I'd suggest getting a good book or books on using PIC's. Right now I'm reading "Programming and Customizing PIC Microcontrollers" by Myke Predko, and the first few chapters are very information packed, perhaps a bit too packed to tell the truth
but from the what I've read it seems to have everyhting you'll need to know for a great working knowledge of using PIC's. It even includes a PCB for a PIC programmer! Go to Amazon and search through, reading the reviews, and find some books that seem to be oriented to your learning style and what you want to learn. edit: the book mentioned also includes a CD, which, among other resources, includes a 100 or so page pdf on programming. Haven't read it yet, but it addresses assembly, basic, and C programming in it.
I'd recomend getting a quality programmer with a ziff socket (makes things so much easier). Then buy a few basic PIC's, like the PIC16F628, which is one I'm using now, do the obligatory LED blink project (microcontroller equivalent of "hello world"), and start making basic project that will do parts of what your final project needs. For example, write a program and create a circuit that turns a power outlet on or off when a button is pressed, then make a clock project, then an LCD project. Then when you're done with that, you should be able make the full project, recycling much of the code you've already written.