City sentiment is fairly complex--I don't understand all of it. Sentiment is worse at Very Hard difficulty than at lower difficulties. If people complain about something (such as high taxes) then you could probably improve city sentiment by changing it, but you could also probably improve city sentiment by doing something else (perhaps raising wages or lowering unemployment).

In Pharaoh (unlike Caesar III), the fraction of people registered for taxes can affect city sentiment. Having no people registered for taxes has the same effect as taxing at 0%. At any given non-zero tax rate, as more people are registered for taxes, the effect becomes worse up to the worst effect at 40%-50% of the people registered for taxes. Depending on the tax rate, some higher fractions of the people registered for taxes may not be quite as bad as 40%-50%. (There is a Taxes thread in the "Links for beginners" sticky thread, but I don't know if the information there is entirely correct.)

Your problem might also be caused by an increase in population, if you typically keep the city small for several years (a reasonable tactic, to earn lots of trade income). City sentiment (like many other things) cannot change much when the population is small.

A recent festival appears to improve city sentiment. If the time since the last festival increases then city sentiment could fall.

Housing levels may have an effect on city sentiment. Some players have suggested that a large difference in housing levels makes city sentiment worse. My guess is that the effect is caused by the worst housing level, so raising the worst housing level improves city sentiment.