Free/Open Source secure Skype alternative on Fedora & OpenBSD?

Well, there are Ekiga and its various cousins eg. Twinkle, which support the SIP standard. Unfortunately my experience is that they do not work as reliably as Skype. In particular, Ekiga seems to get upset by Flash. That is understandable. I also find Flash quite upsetting.

If you can get Ekiga to work, its rates via Diamondcard.us are a lot cheaper than Skype, particularly for SMS, if you use that. The cost of an SMS for the locations I checked is around a third of Skypes. The difference for regular calls is less dramatic but still significant. And it is free (as in freedom) software, and seems to be quite cross-platform.

I think Ekiga does not currently support encryption, so that would violate one of your criteria.

Skype is a proprietary network so to get an open source client you must replace the entire Skype network.

The open source solutions are built around the Asterisk PBX/VOIP server. Asterisk supports SIP and its own IAX protocol. The IAX protocol has optional encryption and requires only one open port on firewalls. Pre-configured linux+asterisk distributions such as Trixbox will get you going. There exists asterisk service providers like teliax.com (and Diamondcard.us mentioned above) that host asterisk servers connecting to other networks (like cell, land lines). AFAICT nobody provides direct connectivity to Skype's network.

http://voip-info.org/ is the best source on asterisk-related VOIP technology.

Many VOIP clients listed here http://www.voip-info.org/wiki/view/Asterisk+IAX+clients . Some support video telephony via webcam, some are cross platform, proprietary and open source codecs must coexist. The setup of all this is truly hideous.

There isn't any yet :( that's the correct answer. But Thank you!

There's Speak Freely & a Windows only version, but development was halted many years ago (Windows7 did not exist, but there was a Windows and a Linux version). So if you fancy picking it up where it was left, that could be an option.

SFLphone (free, opensource from sflphone.org) can be compiled with a video option. It then includes phone calls (audio), video calls, and texting. (I have not persionally tried the video options, but I like the voice features.) It also features optional encryption. Use a good SIP provider (I use Callcentric.com) and it is as reliable as Skype. But it is all open source and non-proprietary.

As mentioned in another answer, there are several open source client options and a variety of SIP providers. If you wish to put in the effort, you can construct your own open alternative to Skype.