Tips for upping the difficulty:
Move up to immortal, but play on a smaller map with fewer AI. Perhaps even a dual map. Fast game speed. Once you beat that, move up to increasingly larger maps with more AI. Eventualy you will be winning a standard game.
I dont really care about turn counts. Everyone says the AI wins at turn ~315 on deity, and I assume they are right, but I dont play at deity

(its too darn frustrating)
I find that if your pursuing a SV, then you should be able to win easily enough by turn 300 pretty much no matter what. There are plenty of threads here describing the basic strategy for a SV in less than 250 turns.
Domination victories are easier with fewer opponents, but harder with shorter games. If you can win a SV or a DV against 3 AI, why not against 6? and then 8. At that point, you should be able to win almost any immortal game.
The main idea is to get used to the pace of the game at immortal, and to feel how the AI / barbarians might behave differently at that level.