Would Skype run on an Arduino

If Skype could run from the command line, without a lot of visual eyecandy, it could be doable

I doubt it, it needs to assemble IP packets into audio output and that is several orders of magnitude of processing power above what the arduino has.