With the launch of FaceTime, video calling on mobile phones has really taken a turn for the upswing. Android's planning its own version of video calling, working on the same basis as FaceTime and already allows you to make video calls via GTalk to other Android devices. However, as is obvious, both of these methods of mobile video calling are platform specific restricted. The way around this is using mobile applications of existing web chat clients like Skype or using a third party application for an existing web chat client like VTok (third party client for Gtalk). Skype is available for iOS, Android, Symbian and Skype on 3 (which you can use on BlackBerry) for free from their respective App Stores/Markets. VTok is also available for free for iOS and Android from the App Store and App Market.
The battle of the screen shots
As far as call quality goes, both are rubbish. I tried using both GRPS (Edge, not 3G unfortunately), as well as Wi-Fi to test the calls from both applications. All calls were going to a PC running the native clients as they come on a PC, so for instance, Skype was done on the desktop application and Gtalk was going to the Gtalk window within Gmail. The mobile applications were being used on an iPhone 4.
Both applications majorly failed on GPRS, for both video and voice calls. Skype would hold its own for about three seconds before the call would get dropped. You'd have three seconds of great video and audio clarity and then the call would fail like a deadbeat whale. Vtok on the other hand was terrible to use on GPRS but the call wouldn't drop. The video was highly pixelated and the sound kept going in and out and I sounded like a robot to the call receiver (I promise, I don't sound like a robot in real life). It was almost like the application was deliberately making the quality of the call so bad that Edge could actually hold it. Between the two, you can't even say there's a clear winner. Yes, 3G would be a better way to test this function, and would definitely support the calls a lot better than Edge but wait till you read about how Wifi held up.
VTok functioned literally the same on Wi-Fi as it did on Edge. The audio was still pretty shady, the video quality was awful and the call still refused to drop. Skype on the other hand worked much better. Sound was awful, but the picture quality was really good. The person on the other end couldn't hear me too well. When they could hear me (the three second sound bite that went through), the quality was actually pretty good and non-robotic. Because I was using Wi-Fi, (and decent Wi-Fi), the call didn't drop at all.
The bottom line is that neither of these applications really gets the job done. If you really had to pick winners, I'd say VTok won on Edge and Skype won on Wi-Fi. On Edge, VTok doesn't drop the call so at the very least, you can still see the other person's face (which helps if you're missing it) continuously, with stutters every three seconds. The real winner out of all of these, at least on Wi-Fi is FaceTime. The calls are crystal clear and the video quality is excellent. But again, the whole point is to be able to make these calls on the go, and not be stranded for Wi-Fi.