1) I also think G&K lacked a unique victory. Not that all expansions needs to have one, but I think a religious victory would have been appropiate. Spread your founded religion to all other civs capitals and/or CS.
2) I know this won't happen until Civ6, but I really loved how you could "visit" a city in Civ1. In Civ5 we can see wonders and buildings on the map, I know, but a better closeup view or possibility to visit the city would be great. Sort of like "walking around" in the city.
3) Palace addons like in Civ1 and Civ2, but with benefits (e.g. observatory / extra painting slots / etc.). This would encourage you to keep citizens happy. Could either happen when you get a golden age through hapiness, or when you get the "We love the king / president day". What I didn't like in Civ 1 and 2 was that there were no benefits (from what I know, but I liked the idea of expanding your palace). To get the "We love the king / president day" you need to get a specific resource. That would even more encourage you to deal with these minor missions within the game.
4) Fluent hapiness motifiers (not just when it goes negative, below -10 and below -20). I really hate this isn't fluent since it doesn't matter if you have -1 or -9 in hapiness.