Just divide the world (or just the game map ;-) in large chunks. Assigns a basic type to each chunk (something like "cool sea", "Desert", "Hot swamp") starting from a point and making the all adjacent tiles of a compatible type (not jungles near arctic .. sorry Kazaar ;-) modified by weather patrons (near the poles, "colder" tiles)

When all the large tiles are assigned, just create smaller tiles (f.ex. 1 character on outdoor map) and randomly generate features that can be found in this terrain (Desert -> 700/1000 Desert 199/1000 stony desert 1/1000 Oasis) following the same pattern that the larger tiles. But near the edges just blend terrain types with the nearest large tile.

In large tiles near a sea tile just create an irregular line or coast (from either beaches or cliffs)

After that just add the rivers (who follow the "lowest" path and change the riverside terrain) and settlements (human, elves, trolls,... according to favoured climates by each race, 1 predominant race per large tile). Give chances to a settlement to change the terrain (creating farms, deforesting..) or check for basic resources before (no water, no people).
(Note: river assignation can be moved to the 1st step)

Some large tiles can be assigned as special tiles that have unique features, in my game one of the sea chunks can have the Mälstron (sp?) a LARGE whirlpool which "sucks" :-) sidesteping some of the normal creation or changing the adjacent tiles.(The crystal palace of the master of ice change all surrounding tiles to "arctic plains")

To add another level of deepness name the large settlement in a tile the capital city of a country (Give some chance that adyacent tiles with the same race be from the same country 50%) and create some international relations (mostly wars)