Is there software that I can teach Illustrator to a client remotely?

My company—Rocky Mountain Training—delivers most of our classes online, and have been doing this for close to 10 years. We were an early adopter of online, interactive, hands-on training led by instructors.

We prefer Citrix's GoTo Meeting (inexpensive) and the more powerful (and more expensive) GoTo Training. Each instructor makes their own decision on which application to use—most of us have used the Citrix products the entire time, but one instructor just retired Connect in favor of GoTo Training. Both applications offer the option to record the classes, and allow the student the option accessing audio via phone or VoIP.

I've used Adobe Connect to demonstrate photoshop (and other advanced tools running at the same time) to my remote students.  It's worked great, and has the ability to record your sessions in case a student drops out and wants to catch the class later.

are the systems any good because Illustrator + screenshare is a asking a lot from your average laptop

If you want to look professional, Adobe Connect is pretty good for this. You can share screens and you can do it to a whole (virtual) room of people too with chat pods for questions, etc.

If you just want to do it quick and easy, a lot of online chatting options like Skype have options for screen sharing.