1.) I cannot say enough good things about Better AI. By the time a putative third expansion is ready to release, Better AI (if current trends continue) will be
awesome.
http://forums.civfanatics.com/forumdisplay.php?f=245.
2.) I have a suggestion for a small improvement to naval combat -- adding a 'patrol' function permitting ships to intercept enemy vessels during the enemy's movement phase, making use of ships to intercept amphbious attacks more effective:
http://forums.civfanatics.com/showthread.php?t=207059
3.) More civs (mainly gravy, but my suggestions include: Ethiopia/Abyssinia (Haile Sellessie), Holland (Wm of Orange), Portugal (Henry), Cherokee (John Ross), Sioux (Sitting Bull), Vietnam (Ho Chi Minh).)
4.) Perhaps a second unique unit/unique building for each civ? (I have always felt that the B-52 should be an American UU, but I digress...) [EDIT: Since someone mentioned it -- give the B-52 a chance to kill units!]
5.) Blind research, as was done in
Sid Meier's Alpha Centauri/Alien Crossfire (SMAC). For those who don't recall, the player had an option in SMAC to choose blind research. If the option was selected, players would not choose their way along the tech tree, but rather would direct researchers to discover military (for example) or population growth related techs; your 'researchers' would then research techs related to that. (So, for instance, if directed to research military techs, animal husbandry or hunting would be researched instead of masonry or agriculture.) Not saying this has to be a default option, but it would be nice to have it added as a variant. I almost always played with this feature on, since I felt it was more realistic than a leader directing which specific technology to research next.