While it's good to familiarize yourself with all the civs, it's probably best to move up levels when you start winning comfortably. Ususally when you advance to the next level, you have to rethink your strategy and play a little more efficiently.
After I beat King pretty easily, I took the advice of another and just moved up to Deity, it took me several tries, but eventually I found a good strategy and won. I didn't really know what I was doing back then, and was still only building about 3-5 cities. It wasn't till I used the Indians "half-cost settlers" that they get in the industrial that I realized that more cities makes everything easier.
Learning to expand will really progress you as a player. Winning the game with all the civs on Deity will help too, and just playing frequently will help you learn so much. Knowing the tech tree is what set me apart when I first started playing online almost a year ago, even though I still wasn't the greatest of players, I got to #2 on H2H in Ps3. I think by winning all 64 victories in Deity, I learned so much about the game that can't just be read about that it really helped me.
Now players are better, and it's quite a jump between multiplayer and Deity. I can win with only one city on Deity, without moving units, or other ways like building a settler at the start of the game and feeding it to the AI, and still pull off a victory. Once you learn how to beat Deity, the AI becomes much less intresting, but it is still a challenge.
So I'd say, once you get a gist of how to beat a particular difficulty, then move up, till you get to Deity, then win at least 16 victories, if not all 64 victory conditions. Then come play me (joke).