For beginners, I imagine the easiest to use are France and America, their bonuses are both very passive and happen throughout the game anyway even if you don't work towards them, and they have main line melee UU's too.
Others that could be fun are the Maya, China, Rome and perhaps Egypt - All the bonuses are not tough to use at a basic level (on warlord!) and are good introductions to different aspects of the game.