I find people on these forums saying deity is too easy. Then I see the same people admitting to re-rolling when getting a non-optimal starting location, trade abusing the AI, pillaging en masse and changing various settings to their advantage prior to starting the game. Try doing all standard settings and not abusing trade or pillage. Then deity can be challenging at least for the first part of the game.
Personally I think the biggest problem of deity is how the AI turns from wolf to lamb the farther in the game you progress.