Well, I'm not a fan of upping the difficulty through the 'level' settings personally. The AI is the AI, the only difference in the difficulty is what effect YOU and how much free crap the AI gets in the start.
What makes for a better game (again in my opinion) is to up the number of AIs on Prince level. As long as they are on the same team, it will automatically get more challenging.
For instance, a 2v6 game on Prince is actually quite challenging. Gave it a go and figured I could just drop one of their caps and mess them all up... that didn't work.
To make it even more challenging, you just have to limit yourself. For instance, if you don't make peace with the AI ever, that makes it even more challenging because you can in theory exploit the fact that they will make peace for deals. Then you rebuild when you were at the brink of death, and attack again.
Anyway, moral of the story, before you increase the difficulty level, try increasing the number of AIs.
I'd be happy to play a 3vwhatever AI with you. My steam ID is the same as my name.
Good luck!