I've actually had a pretty decent experience with Skype on Linux, even with my slow Eee PC. Granted, I don't use video a ton, but it seems to hold up fine when I do. That said, it is certainly missing a lot of the features included in the Windows and Mac versions.

In addition, the Android version lacks video, and is a bit clunky, but I have not had problems with its performance.