Favored changes:
Hex map. I can't really point to any great advantages of a hex grid over a square grid, other than perhaps that diagonals were better than vertical/horizontal, but I really like the look.
Ideologies. I've long felt that ideologies would be a good addition to Civ, although I imagined them differently. The main thing I like about this implementation is that they lead to conflict in the late game, hopefully spicing up the weakest segment. I'd argue that there's too much overlap between the ideologies, though. I like the Social Policies in general although the argument that Tradition is too strong is valid, IMO.
Religion. Civ 5's one religion per civ is arbitrary, but a change for the better, if only to prevent silliness like players hogging three religions. What I like best are the advantages and flavor provided by the distinct choices. I'm surprised that Desert Folklore hasn't been nerfed, though. Desert starts aren't bad, and don't need to be buffed. I think I might like it if the choices were not exclusive. Getting a good pantheon is mostly luck, dependent on the other civs in the game and how the goody hut game goes.
Trade routes. The illusion of realism wears thin by the late game, what with the leader of a great empire scheduling truck routes, but they're a good revival of a mechanic from Civ 2.
Things I miss:
Stacks. One unit per tile looks good and seems like it could be an improvement, yet I don't think it really is all that good an idea. I know the stack of doom was a developer bugbear for years even if it never really seemed to bother the players. The big drawback to it is that the AI can't hack it. I remember the AI pulling off impressive sneak attacks in Civ 3, something I've never seen in Civ V, even in the modern/atomic eras. If the stack of doom really was an issue, stack limits could have addressed the problem-- or any number of other methods, including tactical battles.
Corporations. Sure, they weren't perfect, but I've always liked economic advantages. It might have been nice if trade routes evolved into to monopolies and then to corporations or something.
Warmongering. BNW is a good addition and I like it a lot, but it seems to me that warmongering has been nerfed too hard. Early rushes simply don't appear in the strategy discussions that I read. Unique units are mainly prized for non-war attributes, like pathfinding, and I find that ancient/classical unique units are only provide an advantage in managing barbarians. Complaints about AI passivity are fairly common, and I agree with them. If you do have semi-aggressive neighbors, its usually easy enough to get them to attack somebody who's not you. I miss the big impact that war had in earlier versions, including the vicious dogpiles from Civ 3. It's funny that Civ 4's last expansion emphasized war (at least, that's how I remember it) and Civ 5's made it much less worthwhile.
True start locations for maps based on Earth. This has been requested many, many times throughout Civ 5's history and still not available with the official versions. No idea why it hasn't been included.
Starting technologies. As I recall, nobody gets a starting tech now except the Huns. Techs added a tactical direction, like giving militaristic civs Archery. They could have been used to add some much-needed balance, even to the point of using Civ Rev's trick of giving classical or even medieval technologies (Greeks, for example, started with Democracy in that game, quite a late tech).