CreativeEdge.com has a special going at $19.95 for a month. The Andy Anderson videos for Photoshop and Illustrator are over 10 hours each, cover a lot, and are pretty good. Follow that with some others they have like Power Sessions and you have a good start. Are you planning on buying Adobe CS 5.5?
I think you need both Photoshop and Illustrator to design today but if I had to choose one for wraps, it would be Photoshop.