You can do adultery or murder but what in Islam is the worst sin you can do? Or is it not believing in God/Allah?
Shirk, Associating partners with Allah (SWT), is the greatest sin. Shirk is not 'When you worship other than God', because the root word of Shirk means to associate.
The people of Makkah, and all the previous nations, had no problem with توحيد الربوبية, which means they believed in Allah (SWT) as the creator, but their problem was توحيد الالوهية, which is the Oneness of God. They believed in other Gods along with Allah (SWT), and that is Shirk.
Allah (SWT) says in Surat Al-Ankaboot
If you ask them as to who has created the heavens and the earth and has subjugated the sun and the moon, they will certainly say, “Allah”.(61)
But their problem with the Oneness of God is as described in Surat Al-A'raf (and many other Suras)
They said, “Have you come to us that we should worship Allah alone and give up what our fathers used to worship? (70)
Now, the word Shirk has a broader meaning other than association partners (Idols) with Allah (SWT). The Prophet (PBUH) told us in so many Ahadith, that Showing off is considered Shirk, because you associated someone else in your deed, whether is to get praised by others, or to get a promotion, etc...
Take this Hadith for example (In Sahih Muslim)
“Allah (SWT) said: I am so self-sufficient that I am in no need of having an associate. Thus he who does an action for someone else’s sake as well as Mine will have that action renounced by Me to him whom he associated with Me.”
Simply, if your intention is not sincere to only Allah (SWT), that deed won't be accepted.
Allah knows the best.