So it works fine after turning off SEF? If using SEF ensure the Joomla system SEF plugin is public and published in Extensions > Plugins. If using rewriting ensure mod_rewrite is available and htaccess is properly configured.

Sounds like an issue specifically with SEF then. First step is to ensure live_site in configuration.php is empty. Next navigate to Extensions > Plugins and ensure "System - SEF" is public and published. Once done navigate to Site > Global Configuration and configure SEF as follows.

Search Engine Friendly URLs: Yes
Use URL Rewriting: Yes
Adds Suffix to URL: No
Unicode Aliases: No
Include Site Name in Page Titles: No

Using FTP navigate to Joomla root and rename htaccess.txt to .htaccess. SEF should be fully working now. If not you may want to contact your host and ensure mod_rewrite is working properly.

If issues still persists with SEF then try disabling and purging all forms of caching if enabled. Aside from that I'm unsure what more to advise as it could be a 3rd party extension causing problems with SEF.

Joomla doesn't have a component for SEF. So com_sef shouldn't even exist. Sounds like you've a 3rd party SEF extension installed and are not using Joomlas built in SEF. Could also be leftover files from older Joomla releases. Did you migrate from Joomla 1.x?

Joomla SEF consists of entirely internal library functionality and a system plugin then it uses router.php files in components to handle the rewriting.