Hi,
I would like to suggest that before you go and get yourself a copy of all softwares, use the trial versions of them and get acquainted with it. Once you get to know the basics, you can go ans shell out your hard earned cash. You could also consider open source alternatives if you are a bit adventurous. I personally find the following softwares to be very useful for graphic designing.
1. Photoshop for image manipulation You don;t have to get the latest version, even Photoshop Version 7 should be fine for learning
(GIMP - open source image manipulation program, you could experiment, i'm still to try as i'm glued to photoshop for the moment)
2. Illustrator for vector images. Remember, your clients would use the logos for various purposes, giving them in vector format ensures, you can resize to any resolution, unlike the raster images which can be designed in Photoshop.
3. CorelDraw another vector image program, I personally use much of CorelDraw rather than Illustrator.
4. Inkscape - Open source alternative for Illustrator / CorelDraw.
Last but not the least, all latest Adobe programs like Photoshop / Illustrator use the same familiar interface, so you wouldn't have a steep learning curve if you happen to use them a lot
For the tutorials you find them in tons on the internet, I would suggest you to go to a training center, to get a general knowledge about the programs you are going to use. You can then refer to the advanced tutorials on the internet.
Good luck,
S. Sakthivel