When selecting a civilization for a randomly generated game, choose a civilization that is suited for the map type since certain civilizations have advantages and disadvantages depending on terrain. For example, the Shang do not get any of the triremes, so they're at a disadvantage in a game with a lot of water. You'll need to experiment to find all of these subtle differences, but it will prove to be worth it.
When exploring a random map, players don't need to venture too far away to get up and running. You can always expect to find at least one berry site within approximately 15 tiles of your starting town center, so you might want to explore enough of the map to find that site before placing your granary down. Other resources have similar generalities that you can always count on.
The random map generator does not always place players on opposite ends of the map; if you are in one corner, that does not necessarily mean that your opponent is in the reciprocal position. So, it's always a good idea to explore early to find out where your opponents' towns are located.
More importantly, understand how the map types are defined: Highland means the map is generated entirely of land or land with a small river cutting through it (the land masses will always be connected by several shallows areas). An inland map will always have some water in it, but will still always have a single, unified land mass (though the number of shallows connections will be fewer than in a Highland map). Coastal maps can have separate continents, so you should always plan on having some method of transporting units across the oceans and use fishing boats as an alternative source of food.
A large island map will have a slim chance of being connected by a shallows bridge, but more often large islands make up different continents for multiple players. In many instances players may share an island. Small Island maps create different islands for each player and are never connected by shallows or land bridges. As you become familiar with the advantages and disadvantages for each civilization, you'll be more effective on each terrain type.