Automatic generalization algorithms are not yet a complete solution, they still often make decisions a careful cartographer would abhor. Natural Earth has a good background article
on how their approaches to generalizing features, a multi-step manual process. Axpand claims the Swiss Topography Office had an 80% success rate with automatic generalization when using their software with topographic maps.
You've mentioned in a few responses that you don't like the 'bony' geometries produced by many automated solutions, could you explain what aspects of the data you'd like to retain? Are you interested in positional accuracy of the results, or more in the aesthetics? That will help give us a sense of where a solution might lie.
I have looked at your data and the book example, the problem is that there are three invalid polygons in data that are processed in the book:
GSHHS_l_L1.shp
ID = 92-W
POLYGON ((-180.0 71.514793999999995,-179.69008299999999 71.577888999999999,-178.648889 71.577416999999997,-178.40644399999999 71.549916999999994,-177.406306 71.244167000000004,-177.877444 71.022889000000006,-179.500111 70.863749999999996,-179.93011100000001 70.979583000000005,-180.0 70.962072000000006))
ID = 486-W
POLYGON ((-180.0 -16.799126,-179.84419399999999 -16.691278,-179.80041700000001 -16.789193999999998,-179.850472 -16.878361000000002,-180.0 -16.959561))
GSHHS_l_L2.shp
ID = 7333-W
POLYGON ((-180.0 65.393473,-179.76583299999999 65.428332999999995,-179.95416700000001 65.385555999999994,-179.90972199999999 65.316389,-180.0 65.321635))
Because this is an example it would be easiest to delete those polygons from the dataset or just add one if statement in you code
if geometry.IsValid():
cursor.execute("INSERT INTO gshhs (level, geom) VALUES (%s, ST_GeomFromText(%s, 4326))", (level, wkt))
Best Answer
A topological vector model will provide what you need. In a non-topological storage (such as a shapefile), a single edge between geometries is stored twice. In a topological vector, the areas are stored separately from the lines, so adjustments can be made without effecting topology. I couldn't find a good diagram, so I created this simple example, where the areas A, B and C are computed from the intersections of the lines (connecting 1-4) which separate them.
This model is used by ArcInfo as coverages, in GRASS as its default vector model, and can be used in PostGIS with the experimental PostGIS Topology tool. Perhaps a simpler solution is converting your data into linework, removing the redundant segements, and then recreating your polygons after simplification.