Changing the victory condition can make the game harder, since instead of having the AI duke it out for one of 4 victory conditions, you've pigeonholed them into 2 choices. Ironically, since the AI on king gets few, if any (can't remember), bonuses they're really stuck with science since no one AI will just go crazy with units after getting lucky on their start and neighbors for their initial rush. My guess is you find the AI is stalemate by the industrial/modern era but kicks your butt.
The biggest thing to remember is that the way you "play" on lower difficulty probably needs to be adjusted on higher levels. Before you were probably building the largest most technically advanced military, pumping out wonders like India pumps out babies, and throwing luxuries and gold at your population full of Einstein and Feynman clones living in a perpetual golden age. As you move up to king and beyond, you're really going to have to prioritize. That may mean leaving the pyramids behind even though nobody has built it (for a reason), or building a barracks and a couple of warriors instead of a library and granary in your second or third city.
Maybe leave some science wonders behind for culture, and use them to grab early science helpful polices like commerce (buy libraries) and rationalism. RA agreements are your best friend at harder levels, if you don't use them, the AI will spank you.
Sometimes a science win means having to avoid wars so you can keep production focused on science, and later ss parts. A domination victory doesn't necessarily mean you need the latest generation of units. Out think the AI, put your units on hills and flank, move slow with front-line melee supported by range/arty and you can decimate the modern armor and mech inf. with your regular tanks and inf. Send in sacraficial decoys. I love landing a couple of units behind their lines, having their whole army rush to them and destroy them, only to now have to rush back in time to see their capital fall to my barrage of 3-4 arty and couple of infantry.
Not to sound like a broken record, but city states really do help keep the AI in check. They are usually more upgraded and a bit more difficult to capture, and the AI isn't nearly as smart as you about picking friends and allies. I usually buy off good culture states with good resources, then good maritime states with good resources, then choose between what I really need resource or friend wise. Nothing like buying a city state on the other side of your enemy that will spawn advanced units and hassle them while you go for the prize.
The biggest thing to remember with these guys is that if you leave them alone, they will do the same to you. But you if you are just the slightest friends with them, they'll let you 'quest' for their missions which are sometimes something you are already doing. I love the connect resource and build me a wonder missions, since you are probably going to be doing that anyway... two birds with one stone. Try to be friends with every city-state you don't plan to capture, because these missions give huge boosts to relations.
An extra unit to the AI is useless on harder levels, though I'm not sure the AI pumps out units on king like it can on higher levels... but that extra unit from Edinburgh may be a life saver. Extra culture and food can also really help depending on start position and end-game goals.
And barbarians can be great gold and xp for you, and hilariously funny mortal enemies for the AI. I've seen plenty of civs lose worker after worker to camps way up in the snow because they are too lazy/dumb to go finish it off and park a unit there to clear out the fow. In fact, I usually count on my third worker being a recaptured AI worker/settler.
