I'd say anything with terrain enhancements is a good start.  I'm using USA Extreme Landscapes and I enjoy it.  There's several products for Europe too.  But if you don't mind spending time tinkering, you can get it all for free here:

http://www.simviation.com/fsdterrainsrtm.htm

Hi Sean,

"best payware add-on for FS9"... hard to tell, that depends on personal preferences... but there's a couple of noteworthy add-ons; for a start, it might help you to know how they affect scenery.

I don't know about your knowledge on the mechanics of FS9's scenery, so I'd like to explain these basics, which are essential to understanding what scenery add-ons actually change.

Scenery in FS2004 consists of four different things:
-- Terrain Mesh: Elevation data. The Mesh defines the shape of the terrain. The higher its level of detail (LOD), the more accurate is the representation of hills, mountains, valleys etc. Terrain Meshes are usually based on SRTM data (from NASA's Shuttle Radar Topography Mission); that is real world elevation data!
-- Landclass: Terrain type. Defines what kind of  of terrain a certain area is. (For example: city, small town, grassland, forest, desert etc.)
-- Polygons: Lines that define roads, rivers, coast lines & lakes.
-- Ground Textures: Placed on top of the mesh. Depends on Landclass, part of the world and in-game season. For almost any type of terrain, there are textures for different parts of the world (North America, Europe, Africa, Asia etc.), often in five variations (for spring, summer, fall, winter and hard winter). FS2004 blends the textures, so a city doesn't look like a square, but naturally fades into its surroundings.

Some well-known payware add-ons:
-- FScene. Replacement textures , painted by Ruud Faber. (No mesh/LC!)
-- Ground Environment. Replacement textures, based on aerial photos. (No mesh/LC!)
-- Ultimate Terrain Series. Landclass data and road & water polygons. Based on digitalized maps. Available for Europe, USA and Canada/Alaska. (No mesh/textures!)
-- FS Global, Lago Meshes, FS Genesis Meshes.  (No LC/textures!)
-- Megascenery. Don't know exactly... check out yourself.
There are many other add-ons; VFR sceneries like vfraddons.co.uk offer real-word textures and landmarks, which let the Terrain look like in Google Earth... other add-ons combine mesh, landclass and roads & water data.

I found flightsim.com to be a good source for scenery reviews. Their reviews discuss pros and cons, and contain screenshots, which helps very much making up one's mind. You can google them by typing something like "fscene review site:flightsim.com".

Interesting Freeware:
-- Global SRTM Terrain Mesh @ Simviation
-- UK Scenery Project

There are many more add-ons for you to discover... search, and you will find.

Alright, that's it for now. Happy Flying!

So far I like UT and just picked up global terrain mesh from FSGENSIS.