I have tried to change the site's default language, and this is the language that stays on no matter what ...

Go to JoomSEF's URLs Manager, find the "en" and "fr" SEF URLs and please post their corresponding Real non-SEF URLs.

Home page :
SEF : www.eyevisit4u.com/en
NON SEF : index.php?option=com_hwdvideoshare&lang=en&task=frontpage&Itemid=827

SEF : www.eyevisit4u.com/fr
NON SEF : index.php?option=com_hwdvideoshare&lang=fr&task=frontpage&Itemid=699

The languages seem fine. But on the html code, it doesn't match ...

I have checked on other URLs, they all seem all right. The language tags on SEF and non SEF URLs match perfectly

At one point, I had tried to install JoomFish, but gave up and removed everything since the actual version is not compatible with Joomla 2.5, and I couldn't get the alpha version of Joomfish to work.
I removed all Joomfish related elements, but I still have a com_joomfish in the component list which I cannot get rid of... But I doubt this is the reason for the problem.

Make sure that the System - ARTIO JoomSEF plugin is enabled and that it's ordered as the first of the system plugins.
Also make sure that there's no plugin left from the JoomFish installation, or that it's disabled at least.

Instead of JoomFish, you can try FaLang: extensions.joomla.org/extensions/languag...ingual-content/18210
It's based on JoomFish, but it's made for Joomla 2.5 and latest JoomSEF is compatible with it.