Yeah, and take a reality check too. Playing Prince is a yawnfest. There're only three dificulty levels in Civ5 - Easy (Emperor), Normal (Immortal) and Hard (Deity), anything less than that and the game plays itself.
Well this is pretty condescending, but kudos to you "tough guy".
I actually just beat my first King game. I think I was extremely lucky. The map was continents (large), and I was Alexander. I started the game with China being practically right next to me on this medium-sized continent, nobody else around. So I knew I had to wipe them out asap and with Hoplites it wasn't too difficult at all. I think the barbs destroyed the Chinese settler so I only had to take Beijing.
So once I had the continent all to myself (around 500bc if I remember correctly), I was able to expand and really focus on optimizing my cities. I think this was absolutely key in my victory - I knew the AI sucks at invasions so I didn't need to build many units at all, which has been something that I've struggled with on King. So I was able to build universities, markets, banks etc. all over.
Moreover, the continent was pretty nice with some nice flood river tiles. So basically I had three cities next to these tiles which was an awesome boost to my economy, then a few coastal cities and a couple of nice production cities. I think I had eight cities overall.
However, I knew being isolated had also negative consequences because of the lack or RAs, so I beelined to Astronomy and build a caravel asap. That was also absolutely essential. Every civ I met was friendly because I wasn't a threat. My economy was humming along nicely so I was able to spam RAs and thanks to my many luxury resources, was able to trade them for others so my cities were able to grow.
From then on, it was easier than I expected. I got ahead in techs and got an easy space race victory. Nobody else even built the Apollo Program. But again, I think I was lucky because I had a continent to myself with good resources and tiles.
I played with Alexander because I tried to heed the advice and utilize city states more. I was able to ally with multiple, and I think it really helped too. For the first time I realized they can be very useful, although I had the money to buy them just because I didn't have to focus on my military (in the end I think I had the strongest military just in case, but I was far ahead by then).
So thanks all so far for the tips, I'm so happy I won by first game on King

But then again, next time I'm playing on Pangaea and I need to be ready to defend myself agressively.