On Chieftain, my most common mistake was settling aggressively. I didn't know that it upset the AI when I plopped a city down two squares from theirs. I wondered why they always ended up angry at me.
On Warlord, my most common mistake was refusing demands on principle. This is the level at which I realized principles are too expensive and should be discarded.
On Regent, my most common mistake was shipping off outdated troops (warriors) to defend new cities I was founding on faraway islands. Later I learned to ship the good defenders off, because you can always make better ones in the homeland, where you have barracks and high production.
On Monarch, my most common mistake was trying for too many wonders I couldn't get. After I learned to concentrate on only a few wonders, and prebuild for them, I didn't get into that infuriating spot where you have 5 turns to the Temple of Artemis and someone else gets it and you've got nothing to cascade to. I never hand-build ToA now, only leader-rush or, better, capture it.
On Emperor, my most common mistake so far is trying the super-early archer rush that worked so well for me on Monarch, often getting rid of a nearby Civ so I could expand into twice the territory without further violence. Even if it looks like Zimbabwe is only guarded by a single regular warrior, this never, ever works above Monarch.
I look forward to making more mistakes on higher levels.