I finished on Deity too. When I compare it to my King game, then AI had about the same amount of units, but it researched much faster. That ment better units and cities with higher defence value. It took a bit longer to conquer 5 major civs and happiness was constant issue. In the end I beat the game by 5 or 4 turn I think. I took the upgrade military policy and then went for Liberty and connected all the cities to my capital for 0.5 hapiness. Managed to stay just above "very unhappy" for most part of the game. Also, I took all the city-states that stood in my path for the policy, army and being connected along the road purposes. In the beginning I took great care of the capital too. Built the heroic epic and bought most of the other normal buildings. The main army (which I started conquering on turn 1) went along the silk road and finished at Russia. By that time the second army was conquering Japan and the third was starting to attack India. I was able to research up to the rifles and cavalry, which was very useful against India. Since I left it last, it built up a lot of units and access from the north was soooo tight. Lost many units there. Maybe there's a southern path..