I do like what they're implementing, so I'll focus on stuff they haven't implemented.
I'm in with the colonies/vassals crowd. More specifically :
1) An AI to manage. Puppets serve a similar purpose, but with no control. Why can't I tell them to focus on food/production/science ? Any empire needs middle management I can yell at!
2) On the opposite end of the spectrum, the puppets should also present a challenge. Why aren't the listening ? Is it because they like the ideologies of the another culture ? Are they a flip risk ? They have the mechanic, but having a governor/former Civ leader I can interact with would make a big difference from an immersion perspective.
3) More visible ebb and rise of empires. I acknowledge there may be an ebb and flow to each empires power. The graphs don't tell the story. Make it easier for me to see whats going on. Who traded their way to power ? Who doesn't have critical resources ? How many units did my ally kill in our war ? Who got a lucrative peace deal that set them up for success ? Which AI got boned by barbarians taking their settlers ? A lot of this information can be gleaned from various sources, but I'd like to see an interface that makes it more apparent. As it stands we only see the obvious "they expanded like maniacs" runaways.
4) Random events. I'd happily play at lower levels if there were more challenges that I couldn't directly control. Some of the threads in this sub forum have great ideas on how to balance random events. I'd like to see random events become a setting similar to barbarians. None, normal, raging. As with point 2, its important that I see the impact of a random event on another Civ so I don't fall into "the AI is against me" trap.