I still don't understand why non-"hardcore" players want to play above Prince. Prince is the default difficulty. It's designed for casual players. Maybe your problem is that Prince is too easy rather than King+ being too hard?
I suspect you're right.
I'm not a hardcore player by any stretch (not a good one anyway), though I'm an experienced one (I played all versions since Civ II but never bothered to learn to play the top levels).
Prince is way too easy for me, and I guess Horizons is too experienced the same way I am to get much fun from it. The AI on Prince is no challenge at all.
King is however perfect for casual games for me, unless I get a terrible start in which case I will get a challenge for a while, or be forced to change the VC I originally wanted. Otherwise it's a very forgiving level for me. On Emperor I can't consistently win (not quite) and I play too casually to really enjoy the challenge.
My gripe with pre-patch King is that once I overcome the small bonuses of the AI the mid and late game stops being challenging. I like the "new King" more than pre-patch King. It's a bit more challenging because I spend a longer time in the middle pack and when I get ahead of those I still have the runaway(s) to catch up or I might even have to destroy them around Industrial to prevent their victory.
It's not quite Emperor, but it's a funnier King. It could still be improved, for instance if the AI was more active to prevent a victory.
You don't need to be a hardcore player to play and beat the slightly better AI on King, especially not if you could beat it pre-patch. You just need to borrow the tricks of the hardcore players for the early game, to optimize growth and thus science, after which it's back to the more casual play style, but the catching up phase can be longer than before as the AI is harder to leave behind. Basically you have to say goodbye to more WW than on pre-patch King, unless you have a great start for them. The rest of the level seems to be the same.